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

      0 references
      0 references
      0 references
      26 June 1992
      0 references
      complexity of decision problems
      0 references
      P- and NP-completeness
      0 references
      robust Turing machines
      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

      Identifiers