scientific article; zbMATH DE number 3845567

MaRDI QIDQ3315500zbMATH OpenFDO

Authors J. Hartmanis, Yaacov Yesha

Publication date 1983

zbMATH Keywords

NP-completenesssparse setsEXPTIMEproofs in axiomatized mathematical systems

Mathematics Subject Classification ID

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

Recommendations

• Computation times of NP sets of different densities
• Sparse sets and collapse of complexity classes
• On the Computational Complexity of Small Descriptions
• On the sparse set conjecture for sets with low density
• Sparse sets in NP-P: EXPTIME versus NEXPTIME

Cited in

(3)

• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• Sparse sets and collapse of complexity classes
• Computation times of NP sets of different densities

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 Q3315500)