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.

Rezumat:

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

URL: http://www.springerlink.com/link.asp?id=d4233vp3028g3n83