Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights
✍ Scribed by Peter Jonsson
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 125 KB
- Volume
- 244
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
A boolean constraint satisfaction problem consists of some ÿnite set of constraints (i.e., functions from 0=1-vectors to {0; 1}) and an instance of such a problem is a set of constraints applied to speciÿed subsets of n boolean variables. The goal is to ÿnd an assignment to the variables which satisfy all constraint applications. The computational complexity of optimization problems in connection with such problems has been studied extensively but the results have relied on the assumption that the weights are non-negative. The goal of this article is to study variants of these optimization problems where arbitrary weights are allowed. For the four problems that we consider, we give necessary and su cient conditions for when the problems can be solved in polynomial time. In addition, we show that the problems are NP-equivalent in all other cases.