scientific article; zbMATH DE number 17527

MaRDI QIDQ3974851zbMATH OpenFDO

Authors Carme Àlvarez, J. Díaz, Jacobo Torán

Publication date 26 June 1992

zbMATH Keywords

complexity of decision problemsP- and NP-completenessrobust Turing machines

Mathematics Subject Classification ID

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

Recommendations

• Classes of bounded nondeterminism
• scientific article; zbMATH DE number 176517
• Complexity classes without machines: on complete languages for UP
• Nondeterminism within $P^ * $
• Complexity classes between $\Theta _k^P$ and $\Delta _k^P$

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)