Completeness for nondeterministic complexity classes

DOI10.1007/BF02090397MaRDI QIDQ3979608zbMATH OpenFDO

Authors Harry Buhrman, S. Homer, Leen Torenvliet

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)

Recommendations

• scientific article; zbMATH DE number 176522
• On polynomial-time Turing and many-one completeness in PSPACE
• scientific article; zbMATH DE number 512801
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• On completeness under random reductions

Cites work

• scientific article; zbMATH DE number 4029534 (Why is no real title available?)
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3596249 (Why is no real title available?)
• A comparison of polynomial time completeness notions
• A comparison of polynomial time reducibilities
• Nondeterministic Space is Closed under Complementation
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On log-tape isomorphisms of complete sets
• Relativization of questions about log space computability
• Space-bounded reducibility among combinatorial problems
• The complexity of theorem-proving procedures

Cited in

(22)

• Mirror images and schemes for the maximal complexity of nondeterminism
• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• Introduction to autoreducibility and mitoticity
• scientific article; zbMATH DE number 1500525 (Why is no real title available?)
• Comparing reductions to NP-complete sets
• A comparison of polynomial time completeness notions
• Circuit Definitions of Nondeterministic Complexity Classes
• scientific article; zbMATH DE number 3982519 (Why is no real title available?)
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Non-uniform reductions
• Collapsing degrees via strong computation
• The relative power of logspace and polynomial time reductions
• Dichotomy theorems for families of non-cofinal essential complexity
• Exponential-time and subexponential-time sets
• Partial bi-immunity, scaled dimension, and NP-completeness
• Observations on complete sets between linear time and polynomial time
• Almost-everywhere complexity hierarchies for nondeterministic time
• scientific article; zbMATH DE number 4041256 (Why is no real title available?)
• Computing and Combinatorics
• scientific article; zbMATH DE number 176522 (Why is no real title available?)
• scientific article; zbMATH DE number 1737510 (Why is no real title available?)
• scientific article; zbMATH DE number 4090800 (Why is no real title available?)

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

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