Nondeterminism within P

DOI10.1007/BFB0020811MaRDI QIDQ4035683zbMATH OpenFDO

Authors Jonathan F. Buss, J. Goldsmith

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0020811

zbMATH Keywords

\(P=?\) NPcomplete setsnondeterminism

Mathematics Subject Classification ID

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

Recommendations

• Nondeterminism within $P^ * $
• Classes of bounded nondeterminism
• On nondeterminism in parallel computation
• scientific article; zbMATH DE number 1332665
• scientific article; zbMATH DE number 3903969

Cited in

(27)

• On nondeterminism in parallel computation
• Formalization of the class of problems solvable by a nondeterministic Turing machine
• A source of inconsistency in theories of nondeterministic functions
• On non-determinism in machines and languages
• To the problem P=?NP
• Nondeterministic stack register machines
• Classes of bounded nondeterminism
• Deciding according to the shortest computations
• Nondeterminism through well-founded choice
• scientific article; zbMATH DE number 3846839 (Why is no real title available?)
• Towards separating nondeterminism from determinism
• On Models of a Nondeterministic Computation
• A syntactical definition of the problem
• scientific article; zbMATH DE number 4021119 (Why is no real title available?)
• scientific article; zbMATH DE number 4045156 (Why is no real title available?)
• scientific article; zbMATH DE number 4049046 (Why is no real title available?)
• scientific article; zbMATH DE number 17527 (Why is no real title available?)
• Nondeterminism within $P^ * $
• scientific article; zbMATH DE number 1332665 (Why is no real title available?)
• On the Amount of Nondeterminism and the Power of Verifying
• scientific article; zbMATH DE number 1737510 (Why is no real title available?)
• On digital nondeterminism
• scientific article; zbMATH DE number 827987 (Why is no real title available?)
• Remembering Chandra Kintala
• The emptiness problem for intersections of regular languages
• Turing machines with atoms
• Enumeration kernels for vertex cover and feedback vertex set

This page was built for publication: Nondeterminism within \(P\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4035683)