Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹.

David A. Mix Barrington

Published in: J. Comput. Syst. Sci. (1989)

Keyphrases

polynomial size
exponential size
boolean functions
bounded treewidth
dnf formulas
expressive power
knowledge compilation
search space
uniform distribution
integrity constraints
membership queries