×

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

The main result of the paper consists in the following: there are strong differences in the computational power of deterministic, nondeterministic, co-nondeterministic and alternating eraser Turing machines. The technique of the proof is based on exponential lower and polynomial upper bounds for read-once-only \(\Omega\)- branching programs.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ajtai, M.; Babai, L.; Hajnal, P.; Komlos, J.; Pudlak, P.; Rödl, V.; Szemeredi, E.; Turan, G., Two lower bounds for branching programs, Proc. 18th ACM Symp. on Theory of Computing, 30-38 (1986)
[2] Andreev, A. E., On a method of obtaining lower bounds for the complexity of individual monotone functions, Dokl. Akad. Nauk SSSR, 282, 5, 1033-1037 (1985) · Zbl 0616.94019
[3] Barrington, D. A., Bounded-width polynomial size branching programs recognize exactly those languages in \(NC^1\), Proc. 18th ACM Symp. on Theory of Computing, 1-5 (1986)
[4] Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, J. ACM, 28, 114-133 (1981) · Zbl 0473.68043
[5] Hastad, J., Improved lower bounds for small depth circuits, Proc. 18th ACM Symp. on Theory of Computing, 6-20 (1986)
[6] Immerman, N., Nondeterministic space is closed under complement, Techn. Report 552 (1987), Yale Univ
[7] Karp, R. M.; Lipton, R. J., Some connections between non-uniform and uniform complexity classes, Proc. 12th ACM Symp. on Theory of Computing, 302-309 (1980)
[8] Krause, M., Exponential lower bounds on the complexity of local and real-time branching programs, EIK, 24, 3 (1988)
[9] Kriegel, K.; Waack, S., Exponential lower bounds for real-time branching programs, Inform. Théor. Appl., 24, 4, 447-459 (1988) · Zbl 0664.68046
[10] Meinel, Ch., \(p\)-projection reducibility and the complexity classes \(L\)(nonuniform) and NL(nonuniform), EIK, 23, 545-558 (1987), Extended version · Zbl 0638.68028
[11] b Inform. and Comput., to appear.; b Inform. and Comput., to appear.
[12] Razborov, A. A., A lower bound for the monotone network complexity of the logical permanent, Mat. Zametki, 37, 6 (1985) · Zbl 0584.94026
[13] Skyum, S.; Valiant, L. G., A complexity theory based on Boolean algebra, Proc. 22nd IEEE Symp. on Foundations of Computer Science, 244-253 (1981) · Zbl 0633.68032
[14] Szelepcsenyi, R., The method of forcing for nondeterministic automata, Bull. EATCS, 33, 96-99 (1987) · Zbl 0664.68082
[15] Wegener, I., The Complexity of Boolean Functions (1987), Teubner: Teubner Stuttgart · Zbl 0623.94018
[16] Yao, A. C., Separating the polynomial-time hierarchy by oracles, Proc. 26th IEEE Symp. on Foundations of Computer Science, 1-10 (1985)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.