Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access
From MaRDI portal
Publication:4032302
DOI10.1051/ita/1992260605071zbMath0766.68042MaRDI QIDQ4032302
Publication date: 1 April 1993
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92430
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs, Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
Cites Work
- On uniform circuit complexity
- Modified branching programs and their computational power
- On the complexity of branching programs and decision trees for clique functions
- Nondeterministic Space is Closed under Complementation
- Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
- On the power of parity polynomial time
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item