Advertisement
Published in:
2005 | OriginalPaper | Chapter
Extremal CSPs
Author : Nicolas Prcovic
Published in: Principles and Practice of Constraint Programming - CP 2005
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present a new class of binary CSPs called extremal CSPs. The CSPs of this class are inconsistent but would become consistent if any pair of variable assignments among the forbidden ones was allowed. Being inconsistent, they cannot be solved by any local repair method. As they allow a great number of partial (almost complete) solutions, they can be very hard to solve with tree search methods integrating domain filtering. We experiment that balanced extremal CSPs are much harder to solve than random CSPs of same size at the complexity peak.