I've found this example of constraint propagation using projection rule enter image description here

We have

C = { x1 ≠ x2, x1 ≥ x2 }

< C; x1 ∈ {1,2,3}, x2 ∈ {1,2,3} >

They say that applying propagation rule, does not give any simplification.

I'm not sure why this is the case. Shouldn't we get?

< C; x1 ∈ {2,3}, x2 ∈ {1,2} >

Other steps in the example, make sense that to me, e.g.

< C; x1 ∈ {2}, x2 ∈ {1,2,3} >


< C; x1 ∈ {2}, x2 ∈ {1} >

You apply the propagation rule to a single constraint.

The rules are defined in such a way that they can be applied efficiently. Otherwise, by applying the "generalized propagation rule" you could declare that a SAT instance is unsatisfiable in a single step.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.