Sciweavers

Share
AAAI
2008

A New Incomplete Method for CSP Inconsistency Checking

12 years 4 months ago
A New Incomplete Method for CSP Inconsistency Checking
Checking CSP consistency is shown, in theory, to be an NP-complete problem. There is two families of methods for CSP consistency checking. The first family holds the complete methods which make an exhaustive search on the solution space. These methods have the advantage to prove CSP inconsistency, but their complexity grows exponentially when the problem size increases. The second family includes the incomplete methods that make a local search on the solution space. These methods have been efficiently used to find solutions for large size consistent CSPs that complete methods can not solve. One major drawback of the incomplete methods, is their inability to prove CSP inconsistency. One of the challenges that have been put forward by the CP community (Selman et al. 1997) is to provide incomplete methods that can deal with CSP inconsistency efficiently. The work that we present here, is a contribution towards an answer to this hard challenge. We introduce a new incomplete method for CSP...
Belaid Benhamou, Mohamed Réda Saïdi
Added 02 Oct 2010
Updated 02 Oct 2010
Type Conference
Year 2008
Where AAAI
Authors Belaid Benhamou, Mohamed Réda Saïdi
Comments (0)
books