Talk:Complexity of constraint satisfaction

Missing

• Jeavons et al. approach (Dechter, articles [34,35,36] in Vardi)
• tree decomposition and similar: query decompositio, hyper-tree decomposition; LOGCFL
• conditions based on local consistency missing: 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),
• k-datalog, datalog uniform,
• query rewriting

Tractable classes in Dechter:

• max-closed, CHIP (p. 304-305)
• linear (p. 307)
• row convex (p. 308)
• section 11.4.6 (p. 321-324)
• hybrid tractability (p. 324-326)

Expand the classes of functions for the necessary condition for tractability.

- Liberatore(T) 19:04, 6 April 2006 (UTC)

No mention of "phase transition". Author Barbara Smith and others very important in this. If one is discussing "complexity", discussion of how some seemingly NP complete problems are now solved in linear time is a big event! As time permits I'll find references, but rummaging around 4C is helpful. For one, the nearly linear time solutions in some cases allow for human genome project pattern matching solutions which would not have been possible with exponential time algorithms.

Csp-interest (talk) 08:09, 1 January 2009 (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 columns from a table with all possible 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 selecting 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 from the csp. For example, the disjunction can be obtained by selecting variables cb (note however that the order of the row is not important).

c b
--- 
1 1
0 1
1 0

In order to obtain exactly the solutions as indicated in the 8-column 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. In other words, a constraint is placed over a list of variables if the constraint is satisfied by all possible rows in the table. This way, the relation of all solutions is at least as large as the relation in the 8-columns table above, while at the same time limiting the allowed rows as much as possible. This is a way of placing as many constraints as possible to obtain a set of solution that is as close (possibly with some extra rows/solutions) 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.

- Liberatore(T) 20:35, 5 April 2006 (UTC)