𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of Boolean constraint satisfaction local search problems

✍ Scribed by Philippe Chapdelaine; Nadia Creignou

Publisher
Springer Netherlands
Year
2004
Tongue
English
Weight
129 KB
Volume
43
Category
Article
ISSN
1012-2443

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Boolean constraint satisfaction: complex
Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights
✍ Peter Jonsson πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 125 KB

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 satis

The complexity of constraint satisfactio
The complexity of constraint satisfaction revisited
✍ Alan K. Mackworth; Eugene C. Freuder πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 327 KB

Mackworth, A.K. and E.C. Freuder, The complexity of constraint satisfaction revisited, Artificial Intelligence 59 (1993) 57-62. This paper is a retrospective account of some of the developments leading up to, and ensuing from, the analysis of the complexity of some polynomial network consistency alg

Resolution Complexity of Random Constrai
Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story
✍ Yong Gao; Joseph Culberson πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 97 KB

Let C 2,k,t n,cn be a random constraint satisfaction problem(CSP) of n binary variables, where c > 0 is a fixed constant and the cn constraints are selected uniformly and independently from all the possible k-ary constraints each of which contains exactly t tuples of the values as its restrictions.