scientific article; zbMATH DE number 17527
From MaRDI portal
Publication:3974851
It is known that if \(\text{P}\neq \text{NP}\) then there are sets of intermediate complexity, lying between P and NP-complete, but the existence of complete problems for any of them is not known. The authors study the so-called Bounded-Nondeterminism hierarchy (BND) of classes that have ``natural complete problems, and appear to be strictly between P and NP-complete. The authors obtain a characterization of the classes in BND in terms of one way robust Turing machines, and rise some open questions. [For the entire collection see Zbl 0726.00019.]
Recommendations
Cited in
(7)- Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
- On the classification of NP-complete problems in terms of their correlation coefficient
- Classes of bounded nondeterminism
- Nondeterminism within $P^ * $
- Molecular computing, bounded nondeterminism, and efficient recursion
- The emptiness problem for intersections of regular languages
- The logics for the complexity classes with limited non-determinism
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 Q3974851)