I am interested in showing connection between CSP (Constraint Satisfaction Problems) as it's defined in CSP (definition with Constraint graph, sometimes called binary CSP) and 3SAT problem, when domain of CSP contains of 7 values.

The specific requirement is to show reduction from 3SAT to GAP CSP, when domain of CSP contains of 7 values.

Let try to reduce 3SAT to CSP, every clause of 3SAT can be represent as a vertex of CSP, and edges connect two clauses (vertices) when these clauses have at least one common variable. Set the values (assignments) from the domain of 7 values to every nodes such that to ensure the consistency (each variable get the same value in all clauses).

The problem is I cannot get what is so special about 7 values, apparently, we should have 8 different assignments to the vertices, how can I show that 7 values is enough?

In addition, I still don't have a good intuition about the constraints, for me constraints represented by the edge of the graph, and they ensure the consistency of the assignment (each variable get the same value in all assignments).

Having codded 3SAT as CSP how can we show the reduction to GAP CSP?


Hint: There are seven satisfying assignments to the variables in each clause.

  • $\begingroup$ Thank you, I get your hint, for every clause there are single assignments that doesn't satisfy the clause and it looks like $0 \vee 0 \vee 0$, but for different clauses the unsatisfying assignment is different, but domain is common for all of the clauses, therefore there are should be unsatisfying common assignments, and I don't think it is true. $\endgroup$ – com Jun 28 '13 at 7:57
  • $\begingroup$ the assignment can encode the value of the literals (rather than variables) in the clause, and then you can change the constraints accordingly $\endgroup$ – Sasho Nikolov Jun 28 '13 at 8:42
  • $\begingroup$ @SashoNikolov, thank you for your comment, could you please elaborate a little bit, I don't really get how this answers the question. In addition, it would be great if you could write few words about the intuition behind the constraints, and how they look like in our case. $\endgroup$ – com Jun 28 '13 at 12:30

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.