# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Bounded-width polynomial-size branching programs recognize exactly those languages in $NC\sp 1$. (English) Zbl 0667.68059
The main result is the proof of the equivalence of $NC\sp 1$ (the class of languages recognizable by fan-in two, logarithmic depth circuits) and of ${\cal P}\sb{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 ${\cal N}{\cal C}\sp 1.$ Generalizing the method of proof the author also shows that the word problem for any fixed nonsolvable groups is complete for ${\cal N}{\cal C}\sp 1$ under ${\cal A}{\cal C}\sp 0$ reductions. A list of open problems and a survey of recent progress round off this important paper.
Reviewer: Ch.Meinel

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 68Q05 Models of computation (Turing machines, etc.) 20F10 Decision problems (group theory); connections with logic and automata
Full Text:
##### References:
 [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. Proceedings, 18th ACM STOC, 30-38 (1986) [2] Ajtai, M.: {$\Sigma$}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. Proceedings, 27th IEEE FOCS, 410-417 (1986) [4] D. 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. Proceedings, 18th ACM STOC, 1-5 (1986) [6] Barrington, D. A.: Bounded-width branching programs. Ph.d. thesis, dept. Of mathematics, MIT (May 1986) [7] Barrington, D. A.; Thérien, D.: Finite monoids and the fine structure of NC1. Proceedings, 19th ACM STOC (1987) [8] Beame, P. W.; Cook, S. A.; Hoover, H. J.: Log-depth circuits for division and related problems. Proceedings, 25th IEEE FOCS, 1-6 (1984) · Zbl 0797.68074 [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.: SIAM J. Comput.. 15, 549-560 (1986) [11] Chandra, A. K.; Furst, M. L.; Lipton, R. J.: Multiparty protocols. Proceedings, 15th ACM STOC, 94-99 (1983) [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.: Problems complete for deterministic logarithmic space. (Fév. 1986) · Zbl 0644.68058 [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.: Math. systems theory. 17, 13-27 (1984) [18] Geréb-Graus, M.; Szemerédi, E.: There are no p-complete families of symmetric Boolean functions. (1986) · Zbl 0662.94023 [19] Hastad, J.: Almost optimal lower bounds for small depths circuits. Proceedings, 18th ACM STOC, 6-20 (1986) [20] Hoover, H. J.: Characterizing bounded width, manuscript. (1983) [21] Johnson, D. S.: The NP-completeness column: an ongoing guide. J. algorithms 7, No. No. 2, 289-305 (1986) · Zbl 0608.68033 [22] Ladner, R. E.; Fischer, M. J.: J. assoc. Comput. Mach. 27, 831-838 (1980) [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. M.sc. thesis (May 1976) [25] Meinel, C.: Rudiments of a branching program based complexity theory. (June 1986) [26] Parberry, I.; Schitger, G.: Parallel computation with threshold functions. Lecture notes in computer science 223, 272-290 (1986) [27] Púdlak, P.: A lower bound on complexity of branching programs. Proceedings, conference on the mathematical foundations of computer science, 480-489 (1984) [28] A. A. Razborov, Lower bounds for the size of circuits of bounded depth with basis{&, \oplus}, preprint [Russian]; Math. Notes, in press. · Zbl 0632.94030 [29] Ruzzo, W. L.: On uniform circuit complexity. J. comput. System sci 22, No. 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] J. B. Shearer, personal communications, 1985. [32] Skyum, S.; Valiant, L. G.: J. assoc. Comput. Mach. 32, 484-504 (1985) [33] Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. Proceedings, 19th ACM STOC (1987) [34] Yao, A. C.: Lower bounds by probabilistic arguments. Proceedings, 24th IEEE FOCS, 420-428 (1983) [35] Yao, A. C. C.: Separating the polynomial-time hierarchy by oracles. Proceedings, ACM STOC, 1-10 (1985) [36] Zassenhaus, H. J.: The theory of groups. (1958) · Zbl 0083.24517