×

Separating \(\oplus{}L\), from \(L\), \(NL\), co-\(NL\), and \(AL=P\) for oblivious turing machines of linear access. (English) Zbl 0766.68042

Summary: Using algebraic arguments we derive lower bounds for parity branching programs. Several exponential lower bounds on the width of linear length bounded oblivious parity branching programs are obtained, so for the graph accessibility problem of directed graphs, and the word problem of free groups and one-relator-groups of finite rank. Using well-known results on the simulation of logspace-bounded Turing machines by sequences of branching programs we complete the separation of the complexity classes L, NL, co-NL, \(\oplus\text{L}\), AL=P for oblivious Turing machines of linear access time.

MSC:

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

References:

[1] M. AJTAI, L. BABAJ, P. HAJNAL, J. KOMLOS, P. PUDLAK, V. RÖDEL, E. SZEMEREDI and G. TURAN, Two Lower Bounds for Branching Programs, Proc. 18 ACM-STOC, 1986, pp. 30-39.
[2] N. ALON and W. MAASS, Meanders, Ramsey Theory and Lower Bounds for Branching Programs, Proc. 27th ACM-STOC, 1986, pp. 30-39.
[3] J. CAI and L. HEMACHANDRA, On the Power of Parity Polynomial Time, Proc. STACS’89, Springer Verlag, L.N.C.S., No. 349, pp. 229-239. MR1027404 · Zbl 0718.68038
[4] H. COBHAM, The Recognisation Problem for Perfect Square, Proc. 7-th I.E.E.E. Symp. on SWAT, 1966, pp. 78-87.
[5] C. DAMM and Ch. MEINEL. Separating Completely Complexity Classes Related to Polynomial Size \Omega -Decision Trees, Proc. of FCT’89, L.N.C.S., No. 380, pp. 127-136. Zbl0756.68039 MR1033541 · Zbl 0756.68039
[6] A. HAJNAL, W. MAASS, P. PUDLAK, M. SZEGEDY and G. TURAN, Threshold Circuits of Bounded Depth, Proc. 28 I.E.E.E. Symp. F.O.C.S., pp. 99-110.
[7] N. IMMERMAN, Nondeterministic Space is Closed Under Complement, Techn. Report 552, Yale University, 1987. MR961049 · Zbl 0668.68056
[8] S. JUKNA, Lower Bounds on the Complexity of Local Circuits, Proc. MFCS’86, 1986, L.N.C.S. No. 233, pp. 440-448. Zbl0609.94018 · Zbl 0609.94018
[9] M. KRAUSE, Ch. MEINEL and S. WAACK, Separating the Eraser Turing Machine Classes L, NL, co-NL and P, Proc. of M.F.C.S.’88, Lect. Notes in Compct. Sci, No. 324, pp. 405-413, Theoret. Comput. Sci. (to appear). Zbl0656.68050 MR1023444 · Zbl 0656.68050
[10] M. KRAUSE, S. WAACK and Ch. MEINEL, Separating Complexity Classes Related to Certain Input-Oblivious Logarithmic-Space Bounded Turing-Machines, Proc. I.E.E.E. Structure & Complexity, 1989, Eugenie, U.S.A. · Zbl 0768.68017
[11] M. KRAUSE and S. WAACK, On Oblivious Branching Programs of Linear Length, Proc. of FCT’89, L.N.C.S., No. 380, pp. 287-296 Inform. Comput. (to appear). Zbl0756.68042 MR1127534 · Zbl 0756.68042
[12] Ch. MEINEL, The Power of Polynomial Size \Omega -Branching Programs, Proc. STACS’88, Bordeaux, L.N.C.S. No. 294, pp. 81-90, Inform. Comput. (to appear). Zbl0644.68074 MR935789 · Zbl 0644.68074
[13] Ch. MEINEL, Modified Branching Programs and their Computational Power, Berlin, 1988, in L.N.C.S. No. 370. Zbl0669.68042 MR1009367 · Zbl 0669.68042
[14] C. PAPADIMITRIOU and S. ZACHOS, Two Remarks on the Power of Counting, Proc. 6 th GI Conf. on Theor. Comp. Sci., Springer Verlag, L.N.C.S., No. 145 pp. 269-276. Zbl0506.68039 · Zbl 0506.68039
[15] W. Ruzzo, On Uniform Circuit Complexity, J. Comp. System Sci., 1981, 22, (3), pp. 236-283. Zbl0462.68013 MR633540 · Zbl 0462.68013 · doi:10.1016/0022-0000(81)90038-6
[16] 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
[17] I. WEGENER, On the Complexity of Branching Programs and Decision Trees for Clique Functions, Interner Bericht der Univ. Frankfurt, 1984, in J. of the A.C.M., 1988, 35, pp. 461-471. Zbl0652.68063 MR935261 · Zbl 0652.68063 · doi:10.1145/42282.46161
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.