The Complexity of Approximating Bounded-Degree Boolean #CSP

Martin E. Dyer Leslie Ann Goldberg Markus Jalsenius David Richerby

Published in: CoRR (2009)

Keyphrases

constraint satisfaction problems
computational complexity
real valued
np complete
space complexity
arc consistency
bounded treewidth
machine learning
np hard
worst case
decision makers
decision problems
bounded degree