178 Chapter 8 Constraint Satisfaction Techniques
The encoding of a planning problem into a CSP requires m = k(n + 1) − 1
CSP variables, where n is the number of state variables and k is the bound on the
plan length. However, the domain of each CSP variable can be quite large. It is
important to remark that both CSP and SAT are np-complete problems, whereas
planning, and more precisely the plan-length problem which is of interest to
us here, is pspace- or nexptime-complete (see Section 3.3 and Table 3.2). This
is explained by the fact that the two encodings of planning, into SAT or into a
CSP, lead to a blowup in the size of the resulting problem. For SAT, this blowup
results in an exponential number of Boolean variables. For the CSP encoding, the