Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\). (English) Zbl 0656.68050

Mathematical foundations of computer science, Proc. 13th Symp., Carlsbad/Czech. 1988, Lect. Notes Comput. Sci. 324, 405-413 (1988).
[For the entire collection see Zbl 0643.00024.]
Deterministic, nondeterministic, co-nondeterministic and alternating one- time-only branching programs of polynomial size are considered, which are shown to be equivalent to the respective (nonuniform) logarithmic space- bounded eraser Turing machine models.
The main result of the paper is the separation of all the related complexity classes.
Consequences of this result are, e.g., the proof that uniform logarithmic space-bounded alternating and nondeterministic eraser Turing machines are strictly more powerful than deterministic ones, or that the technique of inductive counting does not work in the case of eraser Turing machines.
Reviewer: C.Meinel


68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)


Zbl 0643.00024