# Is 1-in-k SAT NP-complete for k > 3

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

-

3
Indeed it is NP-Complete. – Geekster Dec 1 '12 at 3:08

## 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)$

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 37, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9319182634353638, "perplexity_flag": "head"}