Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
From MaRDI portal
Publication:1401957
DOI10.1016/S0022-0000(03)00037-0zbMath1054.68056MaRDI QIDQ1401957
Publication date: 19 August 2003
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
OBDDsLower boundsOrdered binary decision diagramsNondeterminismBranching programsSpace complexityGuess-and-verifyOne-way Turing machines
Related Items (2)
On the relative succinctness of sentential decision diagrams ⋮ A hierarchy result for read-once branching programs with restricted parity nondeterminism
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Entropy of contact circuits and lower bounds on their complexity
- Lower bounds for depth-restricted branching programs
- Private vs. common random bits in communication complexity
- On randomized one-round communication complexity
- On limited nondeterminism and the complexity of the V-C dimension
- Classes of bounded nondeterminism
- Graph-Based Algorithms for Boolean Function Manipulation
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- Downward Separation Fails Catastrophically for Limited Nondeterminism Classes
- Branching Programs and Binary Decision Diagrams
- Randomization and nondeterminism are comparable for ordered read-once branching programs
- Communication Complexity
- On the size of randomized OBDDs and read-once branching programs for \(k\)-stable functions
This page was built for publication: Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
