Talk:Complexity of constraint satisfaction
Missing
- Jeavons et al. approach (Dechter, articles [34,35,36] in Vardi)
tree decompositionand similar: query decompositio, hyper-tree decomposition; LOGCFLconditions based on local consistencymissing: row convexity + ???
Definition of uniform and non-uniform csp in terms of the
homomorphism problem. Based on this definition:
dichotomy theorems for non-uniform problems:other result missing?- sufficient general conditions for non-uniform:
negation expressible in Datalog; similar condition for uniform
Relation with other formalisms: join of relations, conjuntive query evaluation/containment, pebble game (relation with strong k-consistency), datalog, datalog uniform, query rewriting
- Liberatore(T) 18:23, 5 April 2006 (UTC)
Universal gadget
The idea is that of placing as many constraints as possible to obtain a set of solutions from which one can extract any possible relation. If a specific relation cannot be obtained this way, it cannot be obtained by combining constraints. A relation with k rows can be written as a table of k rows, in whatever order, for example the following one is the Boolean disjunction:
1 1 0 1 1 0
Since these are columns of three elements, one can consider the above as a selection of a table with 2^3=8 columns:
1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0
If this is exactly the relation expressing the solutions of a csp on eight variables, then every possible relation of three rows can be expressed by selection some variables. For example, one can name the variables as follows:
a b c d e f g h --------------- 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0
If the table expresses exactly the solutions of a csp, then every relation with three rows can be expressed by just selecting a number of variables/rows. For example, the disjunction can be obtained by selecting variables cb (note however that the order of the row is not important).
In order to obtain exactly the solutions as indicated in the table above, one can place a constraint on every list of variables such that the constraint does not remove any sub-row that should be allowed. This way, the resulting total relation is at least as large as the relation on the table above, and restricts variables as much as possible. In a way, this is a way of placing as many constraints as possible to be as close (with some extra rows) to the table above.
If the result of placing these constraints is a set of solutions that is exactly the table above, then every possible relation can be obtained by projecting over a set of variables.
If the set of solution is larger than the table above (there are some solutions that are not rows of the table) some relations may not be expressed, but some others can. A given relation can be obtained by projecting the set of solutions on a set of variables.
A result that can be proved is that this csp expresses exactly all relations that is possible to express; more precisely, whether a relation can be expressed can be checked by looking at the rows that should express it if the set of solutions were exactly the ones of the table above.