Completeness for nondeterministic complexity classes

DOI10.1007/BF02090397zbMATH Open0745.68046MaRDI QIDQ3979608FDOQ3979608

Authors: Harry Buhrman, S. Homer, Leen Torenvliet 

Publication date: 26 June 1992

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

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

zbMATH Keywords

completenessreducibilitiesnondeterministic time and space classes

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (22)

• Mirror images and schemes for the maximal complexity of nondeterminism
• Introduction to autoreducibility and mitoticity
• Title not available (Why is that?)
• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• A comparison of polynomial time completeness notions
• Comparing reductions to NP-complete sets
• Circuit Definitions of Nondeterministic Complexity Classes
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Computing and Combinatorics
• Almost-everywhere complexity hierarchies for nondeterministic time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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)