Consider the following decision problem: 1-in-3SAT Instance: a formula in 3-CNF.

Question

Consider the following decision problem:
1-in-3SAT
Instance: a formula in 3-CNF.
Question: is there some assignment of values to the variables that
makes exactly one literal in each clause true?

Here, the instances are the same as for 3SAT, but the question is different; we need to
decide whether the formula has an assignment that makes exactly one literal in every
clause true. (Our regular satisfi ability problems ask whether there is an assignment that
makes at least one literal in every clause true.)
Prove that 1-in-3SAT is NP-complete. (Hint: To prove NP-hardness, use a reduction from
3SAT. For each clause in the original formula, come up with a set of new clauses that
have a 1-in-3 satisfying assignment if and only if the original clause has a plain satisfying
assignment. This will require the introduction of new variables.)

Explanation / Answer

The reduction is straightforward. As an example, I'll reduce an instance of Exactly-One-in-3SAT to an instance of Unit Intersection.

(x1x4x3)(x4¯¯¯¯¯x2¯¯¯¯¯x3)(x2x1x3¯¯¯¯¯)(x1x4x3)(x4¯x2¯x3)(x2x1x3¯)

Let nn be the number of distinct (positive and negative) literals in the formula, and choose a bijection between the literals and the integers from 11 to nn:

x11x22x33x44x2¯¯¯¯¯5x3¯¯¯¯¯6x4¯¯¯¯¯7x11x22x33x44x2¯5x3¯6x4¯7

The integers on the right are the set XX in the Unit Intersection instance: X={1,2,3,4,5,6,7}X={1,2,3,4,5,6,7}.

Convert each clause in the Exactly-One-in-3SAT instance into a set of integers by using the mapping created earlier to replace literals with integers.

(x1x4x3){1,4,3}(x4¯¯¯¯¯x2¯¯¯¯¯x3){7,5,3}(x2x1x3¯¯¯¯¯){2,1,6}(x1x4x3){1,4,3}(x4¯x2¯x3){7,5,3}(x2x1x3¯){2,1,6}

These are the initial subsets S1...SmS1...Sm in the Unit Intersection instance.

If variables appear as both positive and negative literals in the Exactly-One-in-3SAT instance, for each such variable add a subset that contains the mapped integers for the positive and negative literals of that variable. For our instance we would add

{2,5}{3,6}{4,7}{2,5}{3,6}{4,7}

The reduction is complete. If a subset TT can be found for the Unit Intersection instance, that solution can be mapped back to a satisfying assignment for the Exactly-One-in-3SAT instance.

Consider the problem of "K-3SAT", a variation of 3SAT: Given a 3CNF formula O and an integer k, the machine determines whether the formula O has a satisfying assignment in which at most k variables assigned as "true".

let ff be a 3SAT formula and ww a variable not contained in ff. Then (www¯¯¯¯)f(www¯)f has at least two solutions iff ff has at least one.

Given a 3-SAT formula =C1…Cn=C1…Cn, simply add a new clause with three new variables: Cn+1=y1y2y3Cn+1=y1y2y3.

If x1,…,xnx1,…,xn is a satifying assignment for , then the two different assignments x1,…,xn,y1=true,y2=false,y3=falsex1,…,xn,y1=true,y2=false,y3=false and x1,…,xn,y1=false,y2=true,y3=falsex1,…,xn,y1=false,y2=true,y3=falseboth satisfies the new formula . Vice-versa if is not satisfiable, then is also not satisfiable.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.