scientific article; zbMATH DE number 4029534

MaRDI QIDQ3770515zbMATH OpenFDO

Authors David A. Russo

Publication date 1986

zbMATH Keywords

PSPACEpolynomially levelable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Optimal Approximations and Polynomially Levelable Sets
• E-complete sets do not have optimal polynomial time approximations
• On optimal polynomial time approximations: p-levelability vs. \(\Delta\)-levelability
• Polynomial Time Productivity, Approximations, and Levelability
• The complexity of approximating \(\mathrm{PSPACE}\)-complete problems for hierarchical specifications

Cited in

(12)

• E-complete sets do not have optimal polynomial time approximations
• The structure of generalized complexity cores
• Resource bounded immunity and simplicity
• Completeness for nondeterministic complexity classes
• Effective hull of a set and its approximation
• On optimal language compression for sets in PSPACE/poly
• scientific article; zbMATH DE number 5251723 (Why is no real title available?)
• Collapsing degrees via strong computation
• On optimal polynomial time approximations: p-levelability vs. \(\Delta\)-levelability
• Optimal Approximations and Polynomially Levelable Sets
• On inefficient special cases of NP-complete problems
• Completeness in approximation classes beyond APX

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3770515)