# Connection CSP and 3SAT

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?

• 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. – com Jun 28 '13 at 7:57