zbMATH — the first resource for mathematics

Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\). (English) Zbl 0667.68059
The main result is the proof of the equivalence of \(NC^ 1\) (the class of languages recognizable by fan-in two, logarithmic depth circuits) and of \({\mathcal P}_{bw-BP}\) (the class of languages recognizable by bounded width, polynomial size branching programs) which is one of the most important and surprising results in complexity theory of the last years. In more detail, it is proved that width-5 braching programs as well as width-4 circuits of polynomial size recognize exactly nonuniform \({\mathcal N}{\mathcal C}^ 1.\)
Generalizing the method of proof the author also shows that the word problem for any fixed nonsolvable groups is complete for \({\mathcal N}{\mathcal C}^ 1\) under \({\mathcal A}{\mathcal C}^ 0\) reductions.
A list of open problems and a survey of recent progress round off this important paper.
Reviewer: Ch.Meinel

68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
Full Text: DOI
[1] Ajtai, M.; Barai, L.; Hajnal, P.; Komlós, J.; Kúlak, P.; Rödl, V.; Szemerédi, E.; Turan, G., Two lower bounds for branching programs, (), 30-38
[2] Ajtai, M., σ11 formulae on finite structures, Ann. pure applied logic, 24, 1-48, (1983) · Zbl 0519.03021
[3] Alon, N.; Maass, W., Meanders, Ramsey theory, and lower bounds for branching programs, (), 410-417
[4] {\scD. A. Barrington}, “Width-3 Permutation Branching Programs,” Technical Memorandum TM-293, MIT Laboratory for Computer Science. · Zbl 0797.68075
[5] Barrington, D.A., Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, (), 1-5
[6] Barrington, D.A., Bounded-width branching programs, (), Technical Report TR-361 · Zbl 0837.68056
[7] Barrington, D.A.; Thérien, D., Finite monoids and the fine structure of NC1, ()
[8] Beame, P.W.; Cook, S.A.; Hoover, H.J., Log-depth circuits for division and related problems, (), 1-6
[9] Bennett, C.H., Logical reversibility of computation, IBM J. res. develop., 17, 525-532, (1973) · Zbl 0267.68024
[10] Borodin, A.; Dolev, D.; Fich, F.E.; Paul, W.; Borodin, A.; Dolev, D.; Fich, F.E.; Paul, W., Bounds for width two branching programs, (), SIAM J. comput., 15, 549-560, (1986) · Zbl 0589.68034
[11] Chandra, A.K.; Furst, M.L.; Lipton, R.J., Multiparty protocols, (), 94-99
[12] Chandra, A.K.; Kozen, D.C.; Stockmeyer, L.J., Alternation, J. assoc. comput. Mach., 28, 114-133, (1981) · Zbl 0473.68043
[13] Chandra, A.K.; Stockmeyer, L.; Vishkin, U., Constant-depth reducibility, SIAM J. comput., 13, 423-439, (1984) · Zbl 0538.68038
[14] Cook, S.A., A taxonomy of problems with fast parallel algorithms, Inform. and control, 64, 2-22, (1985) · Zbl 0575.68045
[15] Cook, S.A.; McKenzie, P., (), Publication 560
[16] Fagin, R.; Klawe, M.M.; Pippenger, N.J.; Stockmeyer, L., Bounded depth, polynomial-size circuits for symmetric functions, Theoret. comput. sci., 36, 239-250, (1985) · Zbl 0574.94024
[17] Furst, M.; Saxe, J.B.; Sipser, M.; Furst, M.; Saxe, J.B.; Sipser, M., Parity, circuits and the polynomial time hierarchy, (), Math. systems theory, 17, 13-27, (1984) · Zbl 0534.94008
[18] Geréb-Graus, M.; Szemerédi, E., There are no p-complete families of symmetric Boolean functions, (1986), preprint · Zbl 0662.94023
[19] Hastad, J., Almost optimal lower bounds for small depths circuits, (), 6-20
[20] Hoover, H.J., Characterizing bounded width, manuscript, (1983)
[21] Johnson, D.S., The NP-completeness column: an ongoing guide, J. algorithms, 7, No. 2, 289-305, (1986) · Zbl 0608.68033
[22] Ladner, R.E.; Fischer, M.J.; Ladner, R.E.; Fischer, M.J., Parallel prefix computation, (), J. assoc. comput. Mach., 27, 831-838, (1980) · Zbl 0445.68066
[23] Lee, C.Y., Representation of switching functions by binary decision programs, Bell system tech. J., 38, 985-999, (1959)
[24] Masek, W., A fast algorithm for the string editing problem and decision graph complexity, ()
[25] Meinel, C., Rudiments of a branching program based complexity theory, (June 1986), preprint
[26] Parberry, I.; Schitger, G., Parallel computation with threshold functions, (), 272-290
[27] Púdlak, P., A lower bound on complexity of branching programs, (), 480-489 · Zbl 0572.68033
[28] {\scA. A. Razborov}, Lower bounds for the size of circuits of bounded depth with basis{&, ⊕}, preprint [Russian]; Math. Notes, in press. · Zbl 0632.94030
[29] Ruzzo, W.L., On uniform circuit complexity, J. comput. system sci, 22, No 3, 365-383, (1981) · Zbl 0462.68013
[30] Savage, J., Computational work and time on finite machines, J. assoc. comput. Mach., 19, 660-674, (1972) · Zbl 0251.68031
[31] {\scJ. B. Shearer}, personal communications, 1985.
[32] Skyum, S.; Valiant, L.G.; Skyum, S.; Valiant, L.G., A complexity theory based on Boolean algebra, (), J. assoc. comput. Mach., 32, 484-504, (1985) · Zbl 0633.68032
[33] Smolensky, R., Algebraic methods in the theory of lower bounds for Boolean circuit complexity, ()
[34] Yao, A.C., Lower bounds by probabilistic arguments, (), 420-428
[35] Yao, A.C.C., Separating the polynomial-time hierarchy by oracles, (), 1-10
[36] Zassenhaus, H.J., The theory of groups, ()
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.