On oblivious branching programs of linear length. (English) Zbl 0727.68038

Summary: Input oblivious decision graphs of linear length are considered. Among other concerns the computational complexity of three graph accessibility problems and the word problem of the free group are investigated. Several exponential lower bounds are proved.


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Ajtai, M.; Babai, L.; Hajnal, P.; Komolos, J.; Pudlak, P.; Roedel, V.; Semeredi, E.; Turan, G., Two lower bounds for branching programins, (), 30-39
[2] Alon, N.; Maass, W., Meanders, ramsay theory and lower bounds for branching programs, (), 410-417
[3] Borodin, A.; Cook, S., A time-space tradeoff for sorting on a general sequential model of computation, SIAM J. comput., 11, 1, 287-297, (1982) · Zbl 0478.68061
[4] Dunne, P.E., Lower bounds for the complexity of 1-time-only branching programs, (), 90-99
[5] Krause, M., Exponential lower bounds on the complexity of real-time and local branching programs, J. inform. process. cybernet., 24, 3, (1988)
[6] Krause, M., Lower bounds for depth-restricted branching programs, Inform. comput., 91, 1-14, (1991) · Zbl 0800.68495
[7] Kriegel, K.; Waack, S., Lower bounds on the complexity of real-time branching programs, Informatique théorique et applications/theoret. informat. appl., 22, 4, 447-459, (1988) · Zbl 0664.68046
[8] Lipton, R.J.; Zalcstein, Y., Word problems solvable in logspace, J. assoc. comput. Mach., 24, 3, 522-526, (1977) · Zbl 0359.68049
[9] Magnus, W., Über diskontinuierliche gruppen mit einer definierenden relation (der Freiheitssatz), J. reine angew. math., 163, 141-165, (1930) · JFM 56.0134.03
[10] Magnus, W., Das identitätsproblem für gruppen mit einer definierenden relation, Math. ann., 106, 195-307, (1932) · Zbl 0004.09709
[11] Meinel, Ch., The nonuniform complexity classes \(NC\)^{1}, {\scl}, and \(NL\), J. inform. process. cybernet., 23, 10/11, 545-558, (1987) · Zbl 0638.68028
[12] Meinel, Ch.; Krause, M.; Waack, S., Separating the eraser Turing machine classes \(L_{e}\), \(NLe\), \(co-NLe\), and \(Pe\), (), 405-409
[13] nechiporuk, E.I., On a Boolean function, Dokl. akad. nauk USSR, 169, 4, 765-766, (1966) · Zbl 0161.00901
[14] Wegener, I., On the complexity of branching programs and decision trees for clique functions, J. assoc. comput. Mach., 35, 2, 461-471, (1988) · Zbl 0652.68063
[15] Savitch, W., Relationships between nondeterministic and deterministic tape complexities, J. comput. system sci., 4, 177-192, (1977) · Zbl 0188.33502
[16] Skyum, Waliant L.G., A complexity theory based on Boolean algebra, (), 244-253
[17] Zak, S., An exponential lower bound for one-time-only branching programs, (), 562-566
[18] {\scZak, S.} (manuscript), An exponential lower bound for real-time braching programs.
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.