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