1

I'm looking over previous exam papers, and have come across this question which has confused me.

Question:

Convert the Not-All-Equal 2-SAT problem given by the clauses {x1, x2}, {x2, x3}, {x3, x4}, {x4, x5}, {x5, x1} to an equivalent 2-SAT problem. (Hint: the 2-SAT problem contains 10 clauses).

From my understanding, is this simply finding the negation for each literal in every clause? So for example, {x1, x2} = {-x1, -x2}, and this is done for each clause? Is this correct?

Richard Erickson
  • 2,568
  • 8
  • 26
  • 39
user6227505
  • 19
  • 2
  • Clearly your solution has the right number of clauses, so all you need to do is prove (to yourself, at least) that an arbitrary satisfying solution to NAE-2-SAT also satisfies your constructed instance of 2-SAT, and vice versa. – j_random_hacker May 04 '16 at 14:35
  • Thanks for the reply, one question, what if the NAE2AT problem cannot be satisfied? – user6227505 May 04 '16 at 15:07
  • Actually if you have proven both directions of the "satisfying" case, then you don't need to worry about that possibility :) To see why, suppose that there is no solution to the NAE-2-SAT problem. Since you have proven that *any* satisfying solution to the 2-SAT instance you constructed will also be a satisfying solution to the NAE-2-SAT problem, it must be that there is also no satisfying solution to the 2-SAT instance -- since if there was one, that solution would also satisfy the NAE-2-SAT instance, which contradicts the assumption that it has no solutions. – j_random_hacker May 06 '16 at 12:11
  • While it's more natural to try proving that both "If an assignment x solves the NAE-2-SAT instance then x solves the 2-SAT instance" and "If no assignment solves the NAE-2-SAT instance then no assignment solves the 2-SAT instance", it's often much easier to *prove* results like this by changing the second branch to its logically equivalent contrapositive form: here, "If some assignment solves the 2-SAT instance then some assignment solves the NAE-2-SAT instance". (Note that we don't even need to show that *the same* assignment works.) – j_random_hacker May 06 '16 at 12:25

1 Answers1

2

That is correct. Specifically, replace all clauses (x ∨ y) with (x ∨ y) ∧ (~x ∨ ~y). That literally says "x or y have to be true, and x or y have to be false", or equivalently "satisfy (x ∨ y) while making sure that one of x and y is false".

To prove the equivalence, let us first assume that the NAE 2-SAT problem is satisfiable. Let A be a satisfying assignment and let {x, y} be one arbitrary clause. Since exactly one of x and y are true, this implies that (x ∨ y) ∧ (~x ∨ ~y) is true. Hence, the corresponding two clauses in the 2-SAT formula are satisfied. Since {x, y} was chosen arbitrarily, we conclude that A satisfies all the clauses in the 2-SAT formula.

Conversely, let us assume that the NAE 2-SAT is not satisfiable. That is, for any assignment, there exists some clause {x, y} for which x and y are either both true or both false. Let A be an arbitrarily chosen assignment and let {x, y} be a clause that A does not satisfy (in the NAE 2-SAT). Since x = y, this implies that (x ∨ y) ∧ (~x ∨ ~y) is false (because one of the halves of the conjunction will be false). Hence, A does not satisfy the 2-SAT formula. Since A was chosen arbitrarily, we conclude that no assignment satisfies the 2-SAT formula.

Cătălin Frâncu
  • 1,179
  • 8
  • 15