scientific article; zbMATH DE number 3845567

zbMATH Open0533.03023MaRDI QIDQ3315500FDOQ3315500

Authors: J. Hartmanis, Yaacov Yesha 

Publication date: 1983

Title of this publication is not available (Why is that?)

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

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)

Cited In (3)

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

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)