Constraint satisfaction dual problem: Difference between revisions

Revision as of 03:44, 2 March 2007

Revision as of 08:34, 6 June 2007

Line 3:

==The dual problem==

The dual problem of a constraint satisfaction problem contains a variable for each constraint of the original problem. Its domains and constraints are buildbuilt so to enforce a sort of equivalence to the original problem. In particular, the ___domain of a variable of the dual problem contains one element for each tuple satisfying the corresponding original constraint. This way, a dual variable can take a value if and only if the corresponding original constraint is satisfied by the corresponding tuple.

The constraints of the dual problem forbid two dual variables to take values that correspond to two incompatible tuples. Without these constraints, one dual variable may take the value corresponding to the tuple <math>x=1,y=2</math> while another dual variable takes the value corresponding to <math>y=3,z=1</math>, which assigns a different value to <math>y</math>.