[CSP Thinking cap]

["Subbarao Kambhampati" <rao@asu.edu>]

Here are some things you can think of:

 

1. Have you played Sudoku--if so, can you illustate how what you do in sudoku wind up being equivalent to the various CSP heuristics?

 

 

2. Suppose we have three CSP problems:

 

 1.  20 variables and 5 (binary) constraints.

 2.  40 variables and 200 (binary) constraints

 3. 200 variables and 199,000 (binary) constraints

 

Which of the CSP problems above do you think will be easiest to solve? Which will be the hardest?

(assume that all constraints have about the same tightness).

 

3. For the CSP search algorithms we discussed in the class, does it matter whether the constraints are represented as (a) legal partial assignments (b) illegal partial assignments (c) pieces of code that take a partial assignment and return a boolean saying Yes/No.

 

 

4. A subclass S of a problem class P is considered canonical if every instance of P can be "compiled down" to a *finite* instance of S. For example, the class of "programs written in Intel m/c language" is a canonical class of all programs. (Instead of "finite" we might also consider compilations that are only *polynomially larger*--but ignore it for now).

 

 4.1 (easy) Argue that SAT (i.e., boolean stisfiability problems) are a canonical class of CSP problems.

 

 4.2 (harder) Argue that *Binary CSP* problems are a canonical class of CSP problems

 

 

5. (If you know Linear programming and Integer Programming). Argue that every 0-1 integer programming problem with constant objective function can be compiled down to CSP.

 

 

Rao