1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jun 28, 2013 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
    Commented Jun 28, 2013 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
    Commented Jun 28, 2013 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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