Optimal Approximations and Polynomially Levelable Sets

DOI10.1137/0215027zbMath0644.68054OpenAlexW1964186004MaRDI QIDQ3787474

David A. Russo, Pekka Orponen, Uwe Schoening

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215027

zbMATH Keywords

computational complexityapproximation algorithmspolynomial reductionspaddabilitypolynomial levelabilityintractable setsself reducibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (18)

Some remarks on witness functions for nonpolynomial and noncomplete sets in NP ⋮ Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ A classification of complexity core lattices ⋮ The structure of generalized complexity cores ⋮ Notes on polynomial levelability ⋮ Better approximations of non-Hamiltonian graphs ⋮ An efficient case for computing minimum linear arboricity with small maximum degree ⋮ E-complete sets do not have optimal polynomial time approximations ⋮ Approximation of coNP sets by NP-complete sets ⋮ Productive functions and isomorphisms ⋮ OnP-subset structures ⋮ On sets polynomially enumerable by iteration ⋮ On optimal polynomial time approximations: P-levelability vs. δ-levelability ⋮ Exponential-time and subexponential-time sets ⋮ On the size of classes with weak membership properties ⋮ On inefficient special cases of NP-complete problems ⋮ Genericity, Randomness, and Polynomial-Time Approximations ⋮ Resource bounded immunity and simplicity

This page was built for publication: Optimal Approximations and Polynomially Levelable Sets