Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0667.68059
Barrington, David A.
Bounded-width polynomial-size branching programs recognize exactly those languages in $NC\sp 1$. (English)
[J] J. Comput. Syst. Sci. 38, No.1, 150-164 (1989). ISSN 0022-0000

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.$ \par 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. \par A list of open problems and a survey of recent progress round off this important paper.
[Ch.Meinel]

MSC 2000:: *68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation
20F10 Decision problems (group theory)

Keywords: word problem for nonsolvable groups; $NC\sp 1$; bounded width; branching programs

Cited in: Zbl 0946.68046 Zbl 0764.68040 Zbl 0766.68040 Zbl 0743.68062 Zbl 0797.68075

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]