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.]











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)