Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
From MaRDI portal
Publication:1178711
DOI10.1016/0304-3975(91)90021-SzbMath0749.68036MaRDI QIDQ1178711
Stephan Waack, Matthias Krause, Christoph Meinel
Publication date: 26 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (18)
On lower bounds for read-\(k\)-times branching programs ⋮ A simple function that requires exponential size read-once branching programs ⋮ On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width ⋮ Nondeterministic unitary OBDDs ⋮ Reordering method and hierarchies for quantum and classical ordered binary decision diagrams ⋮ Exponential space complexity for OBDD-based reachability analysis ⋮ Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines ⋮ Neither reading few bits twice nor reading illegally helps much ⋮ Approximation of boolean functions by combinatorial rectangles ⋮ Almost \(k\)-wise independence and hard Boolean functions. ⋮ A note on read-$k$ times branching programs ⋮ Separating complexity classes related to \(\Omega\)-decision trees ⋮ Quantum branching programs and space-bounded nonuniform quantum complexity ⋮ On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem ⋮ On the size of (generalized) OBDDs for threshold functions ⋮ A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs ⋮ A hierarchy result for read-once branching programs with restricted parity nondeterminism ⋮ A very simple function that requires exponential size read-once branching programs.
Cites Work
This page was built for publication: Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
