The complexity of counting locally maximal satisfying assignments of Boolean CSPs

We investigate the computational complexity of the problem of counting the locally maximal satisfying assignments of a Constraint Satisfaction Problem (CSP) over the Boolean domain {0, 1}. A satisfying assignment is locally maximal if any new assignment which is obtained from it by changing a 0 to a...

全面介绍

书目详细资料
Main Authors: Goldberg, L, Jerrum, M
格式: Journal article
出版: Elsevier 2016