Local consistency notions
Krzysztof Rafal Apt · Cambridge University Press eBooks · 2003
IDEALLY, WE WOULD like to solve CSPs directly, by means of some efficient algorithm. But the definition of a CSP is extremely general, so, as already mentioned in Chapter 1, no universal efficient methods for solving them exist. Various general techniques were developed to solve CSPs and in the absence of efficient algorithms a combination of these techniques is a natural way to proceed. In Chapter 3 we explained that the main idea is to reduce a given CSP to another one that is equivalent but easier to solve. This process is called constraint propagation and the algorithms that achieve this reduction are called constraint propagation algorithms. They are discussed in Chapter 7. These algorithms usually aim at reaching some form of ‘local consistency’. Several forms of local consistency have been defined but it is not clear how to provide a satisfactory formalisation of this notion. So we rather confine ourselves to a review of the most common types of local consistency. Informally, local consistency means that some subparts of the considered CSP are in a ‘desired form’, for example consistent. To achieve a smooth transition between this chapter and Chapter 7, each time we introduce a notion of local consistency we also provide its characterisation. These characterisations are then used in Chapter 7 to generate the appropriate constraint propagation algorithms. They are based on the proof theoretic framework introduced in Section 4.1.