Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.

DOI10.1016/S0022-0000(03)00037-0MaRDI QIDQ1401957zbMATH OpenFDO

Authors Martin Sauerhoff

Publication date 19 August 2003

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0022-0000(03)00037-0

zbMATH Keywords

Branching programsGuess-and-verifyLower boundsNondeterminismOBDDsOne-way Turing machinesOrdered binary decision diagramsSpace complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• scientific article; zbMATH DE number 1500659
• An improved hierarchy result for partitioned BDDs
• Nondeterministic unitary OBDDs
• Very narrow quantum OBDDs and width hierarchies for classical OBDDs
• Lower Bounds for Testing Computability by Small Width OBDDs

Cites work

• Branching Programs and Binary Decision Diagrams
• Classes of bounded nondeterminism
• Communication Complexity
• Downward Separation Fails Catastrophically for Limited Nondeterminism Classes
• Entropy of contact circuits and lower bounds on their complexity
• Graph-Based Algorithms for Boolean Function Manipulation
• scientific article; zbMATH DE number 17527 (Why is no real title available?)
• scientific article; zbMATH DE number 1335889 (Why is no real title available?)
• scientific article; zbMATH DE number 1332665 (Why is no real title available?)
• scientific article; zbMATH DE number 1011685 (Why is no real title available?)
• scientific article; zbMATH DE number 1500514 (Why is no real title available?)
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• Lower bounds for depth-restricted branching programs
• On limited nondeterminism and the complexity of the V-C dimension
• On randomized one-round communication complexity
• On the size of randomized OBDDs and read-once branching programs for k-stable functions
• Private vs. common random bits in communication complexity
• Randomization and nondeterminism are comparable for ordered read-once branching programs

Cited in

(7)

• On the relative succinctness of sentential decision diagrams
• Nondeterministic unitary OBDDs
• A hierarchy result for read-once branching programs with restricted parity nondeterminism
• On Models of a Nondeterministic Computation
• Testing Computability by Width Two OBDDs
• On the Amount of Nondeterminism and the Power of Verifying
• scientific article; zbMATH DE number 1500659 (Why is no real title available?)

This page was built for publication: Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.

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