Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
type: Item
instance of: scholarly article
title: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
zbMATH Open document ID: 0667.68059
DOI: 10.1016/0022-0000(89)90037-8
author: David A. Barrington
published in: Journal of Computer and System Sciences
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 20F10
zbMATH DE Number: 4092774
zbMATH Keywords: word problem for nonsolvable groups
zbMATH Keywords: \(NC^ 1\)
zbMATH Keywords: bounded width
zbMATH Keywords: branching programs
Wikidata QID: Q29543597
MaRDI profile type: Publication
full work available at URL: 0022-0000(89)90037-8
OpenAlex ID: W4240781210
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: Q4302457
cites work: Superlinear lower bounds for bounded-width branching programs
cites work: Logical Reversibility of Computation
cites work: Bounds for Width Two Branching Programs
cites work: Alternation
cites work: Constant Depth Reducibility
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Bounded-depth, polynomial-size circuits for symmetric functions
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: There are no p-complete families of symmetric Boolean functions
cites work: The NP-completeness column: An ongoing guide
cites work: Parallel Prefix Computation
cites work: Q3751010
cites work: Q3690219
cites work: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
cites work: On uniform circuit complexity
cites work: Computational Work and Time on Finite Machines
cites work: A complexity theory based on Boolean algebra
cites work: Q3256242
description: scientific article; zbMATH DE number 4092774