Publication:3804193
From MaRDI portal
zbMath0656.68050MaRDI QIDQ3804193
Christoph Meinel, Stephan Waack, Matthias Krause
Publication date: 1988
nondeterminism; \(\Omega\)-branching programs; eraser Turing machines; separating complexity classes
68Q25: Analysis of algorithms and problem complexity
Related Items
Unnamed Item, On oblivious branching programs of linear length, Polynomial size \(\Omega\)-branching programs and their computational power, Problems complete for \(\oplus L\), Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access