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

Krause, Matthias; Meinel, Christoph; Waack, Stephan

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

MSC:

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

Keywords:

\(\Omega\)-branching programs; nondeterminism; separating complexity classes; eraser Turing machines

Citations:

Zbl 0643.00024