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

David A. Mix Barrington

Published in: STOC (1986)

Keyphrases

polynomial size
bounded treewidth
exponential size
boolean functions
dnf formulas
knowledge compilation
expressive power
np complete
learning algorithm
uniform distribution
information extraction
constraint satisfaction
target language