No label defined (Q3974851)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 17527
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 17527 |
Statements
26 June 1992
0 references
complexity of decision problems
0 references
P- and NP-completeness
0 references
robust Turing machines
0 references
0.8125428557395935
0 references
0.7617484331130981
0 references
0.7617484331130981
0 references
0.7617483735084534
0 references
0.750460147857666
0 references
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.]
0 references