Inscriere cercetatori


Counting, Structure Identification and Maximum Consistency for Binary Constraint Satisfaction Problems

Domenii publicaţii > Ştiinţe informatice + Tipuri publicaţii > Articol în volumul unei conferinţe

Autori: Gabriel Istrate

Editorial: G. Smolka, Springer Verlag, Lecture Notes in Computer Science 1330, Proceedings of the Third International Conference on Principles and Practice of Constraint Programming - CP 1997, Linz, Austria, p.136-149, 1997.


Using a framework inspired by Schaefer’s generalized satisfiability model [Sch78], Cohen, Cooper and Jeavons [CCJ94] studied the computational complexity of constraint satisfaction problems in the special case when the set of constraints is closed under permutation of labels and domain restriction, and precisely identified the tractable (and intractable) cases.
Using the same model we characterize the complexity of three related problems:
1. counting the number of solutions.
2. structure identification (Dechter and Pearl [DP92]).
3. approximating the maximum number of satisfiable constraints.

Cuvinte cheie: constraint programming, computational complexity