Monday, September 17, 2007

[CSP Thinking cap]

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
 
 
 

1 comment:

Vidya said...

1.
When we play SUDOKU, we end up doing the same kinds of calculations that a CSP solving system would - basing heuristics on constraints.
- We look at the row/column/block that is most populated, and try solving that first.
This is nothing but the Most Constrained Variable First principle.
- When a number is found, we look for finding the same number elsewhere, or other numbers in the same row/column/block.
This way, we are looking at solutions to variables for which contraints have increased by the recent solution discovery.
- However, there is no scope for Least Constraining Value selection, since each variable permits only a single value.