×
Krause, Matthias; Meinel, Christoph; Waack, Stephan

Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines. (English) Zbl 0768.68017

RAIRO, Inform. Théor. Appl. 26, No. 4, 345-362 (1992).
Summary: In the following we prove that input oblivious simultaneously linear access-time and logarithmic space-bounded nondeterministic Turing machines are more powerful than deterministic ones. Moreover, we separate all the corresponding complexity classes \(L_{0,\text{lin}}\), \(NL_{o,\text{lin}}\), \(\text{co-}NL_{0,\text{lin}}\) and \(P=AL_{0,\text{lin}}\) from each other.

Cited in 5 Documents

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

logarithmic space-bounded nondeterministic Turing machines
PDF BibTeX XML Cite
\textit{M. Krause} et al., RAIRO, Inform. Théor. Appl. 26, No. 4, 345--362 (1992; Zbl 0768.68017)
Full Text: DOI EuDML
  • logo of hbz
  • logo of WorldCat

References:

[1] N. ALON and W. MAASS, Meanders, Ramsey Theory and Lower Bounds, Proc. 27th I.E.E.E. FOCS 410-417, 1986.
[2] N. IMMERMAN, Nondeterministic Space is Closed Under Complement, Techn. Report 552, Yale Univ., 1987. MR961049 · Zbl 0668.68056
[3] R. M. KARP and R. J. LIPTON, Some Connections Between Nonuniform and Uniform Complexity Classes, Proc. 12th A.C.M. Symp. on Theory of Computing, 302-309 1980.
[4] M. KRAUSE, Ch. MEINEL and S. WAACK, Separating the Eraser Turing Machine Classes Le, NLe, co-NLe and Pe, Theoret. Comput. Sci., 1991, 86, pp. 267-275. Zbl0749.68036 MR1122791 · Zbl 0749.68036
[5] M. KRAUSE, Lower Bounds for Depth-Restricted Branching programs, Inform. and Comput., 1991, 91, pp. 1-14. Zbl0800.68495 MR1097261 · Zbl 0800.68495
[6] M. KRAUSE and S. WAACK, On Oblivious Branching Programs of Linear Length, Inform. and Comput., 1991, 94, pp. 232-249. Zbl0727.68038 MR1127534 · Zbl 0727.68038
[7] Ch. MEINEL, p-Projection Reducibility and the Complexity Classes L (Nonuniform) and NL (Nonuniform), Proc. 12th MFCS, Bratislava, LNCS 233, pp.527-535; revised and extended version in EIK, 1987, 23, 10/11, pp. 545-558. Zbl0611.03021 MR935269 · Zbl 0611.03021
[8] Ch. MEINEL, The Power of Polynomial Size \Omega -Branching Programs, Proc. STAC’88, Bordeaux, L.N.C.S. n^\circ 294, pp. 81-90. Zbl0644.68074 MR935789 · Zbl 0644.68074
[9] W. Ruzzo, On Uniform Circuit Complexity, J. Comput. System Sci., 1981, 22, (3), pp. 236-283. Zbl0462.68013 MR633540 · Zbl 0462.68013
[10] S. SKYUM and L. VALIANT, A Complexity Theory Based on Boolean Algebra, Proc. 22th LE.E.E. F.O.C.S., 1981, pp. 244-253. · Zbl 0633.68032
[11] R. SZELEPCSENYI, The Method of Forcing for Nondeterministic Automata, Bulletin of the E.A.T.C.S., 1987, 33, pp. 96-99. Zbl0664.68082 · Zbl 0664.68082
[12] I. WEGENER, The Complexity of Boolean Functions, Teubner, Stuttgart, 1987. Zbl0623.94018 MR905473 · Zbl 0623.94018
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.