Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

It is well-known that 1-in-k SAT is NP-complete for k=3. What about for k > 3?

share|improve this question
3  
Indeed it is NP-Complete. –  Tayfun Pay Dec 1 '12 at 3:08
add comment

migrated from cstheory.stackexchange.com Dec 2 '12 at 6:21

This question came from our site for theoretical computer scientists and researchers in related fields.

1 Answer

It's still in NP by using a truth assignment as a proof.

You can reduce 1-in-3 SAT to 1-in-$k$ SAT to show hardness as follows. Let $\phi$ be an instance of 1-in-3 SAT with clauses $C_i$ for $1 \le i \le m$. For each $C_i$ we define $C_i'$ by adding $k - 3$ instances of the literal $y$ (where $y$ is a new variable that does not appear in any $C_i$). We also construct the new clause $C_{m+1}'$ which has $k-1$ occurences of the literal $y$, and one occurence of the literal $\neg y$. Let $\phi'$ be the instance of 1-in-$k$ SAT with clauses $C_i'$ for $1 \le i \le m+1$. I claim $\phi'$ is a YES-instance of 1-in-$k$ sat if and only if $\phi$ is a YES-instance of 1-in-3 SAT.

First, assume $\phi'$ is a YES-instance, and choose a satisfying assignment. $C_{m+1}'$ is satisfied only when $y$ is false, so this assignment has $y$ false. Therefore, the literals $x$ are not satisfied, and so exactly one of the first 3 literals of $C_i'$ is satisfied for each $i$. These are exactly the literals of $C_i$, so exactly one of the literals of $C_i$ is satisfied for each $C_i$ and so $\phi$ is a YES-instance.

In the other direction, suppose $\phi$ is a YES-instance, and choose a satisfying assignment. Extend this assignment to give $y$ the value falsehood. This assignment shows that $\phi'$ is a YES-instance.

To illustrate the reduction, here is an example (going to 1-in-5 SAT):

$\phi = (x_1 \vee \neg x_1 \vee x_2) \wedge (x_3 \vee \neg x_2 \vee \neg x_2)$

$\phi' = (x_1 \vee \neg x_1 \vee x_2 \vee y \vee y) \wedge (x_3 \vee \neg x_2 \vee \neg x_2 \vee y \vee y) \wedge (y \vee y \vee y \vee y \vee \neg y) $

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.