Completeness for nondeterministic complexity classes

DOI10.1007/BF02090397zbMath0745.68046MaRDI QIDQ3979608

Harry Buhrman, Leen Torenvliet, Homer, Steven

Publication date: 26 June 1992

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

completenessreducibilitiesnondeterministic time and space classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

Collapsing degrees via strong computation ⋮ Comparing reductions to NP-complete sets ⋮ Introduction to Autoreducibility and Mitoticity ⋮ Non-uniform reductions ⋮ Cook versus Karp-Levin: Separating completeness notions if NP is not small ⋮ Partial bi-immunity, scaled dimension, and NP-completeness ⋮ Collapsing and separating completeness notions under average-case and worst-case hypotheses ⋮ Exponential-time and subexponential-time sets ⋮ The relative power of logspace and polynomial time reductions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A comparison of polynomial time completeness notions
• Space-bounded reducibility among combinatorial problems
• A comparison of polynomial time reducibilities
• On log-tape isomorphisms of complete sets
• Nondeterministic Space is Closed under Complementation
• Relativization of questions about log space computability
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The complexity of theorem-proving procedures

This page was built for publication: Completeness for nondeterministic complexity classes