Optimal Approximations and Polynomially Levelable Sets
From MaRDI portal
Publication:3787474
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
computational complexityapproximation algorithmspolynomial reductionspaddabilitypolynomial levelabilityintractable setsself reducibility
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