Reduce 4-SAT to 5-SAT

given is a reduction from 4-SAT to 5-SAT. How is it possible to describe such a function? I found some informations about reduction 3-SAT to 4-SAT here, but it can't help me so much.

• Can you define your version of $k$-SAT? – Yuval Filmus May 21 at 10:29
• k-SAT = { F | F is a satisfiable Boolean formula in k-CNF } – samTT May 21 at 10:31
• What’s $k$-CNF for you? – Yuval Filmus May 21 at 10:57
• Can you also explain what you don't understand in the linked answer? The reduction from 4-SAT to 5-SAT is essentially the same as the reduction from 3-SAT to 4-SAT. – Yuval Filmus May 21 at 14:54
• To make @YuvalFilmus's question more specific, does "$k$-CNF" mean that each clause has at most $k$ literals, or exactly $k$ literals? – David Richerby May 21 at 21:45

Here is a translation of the answer how to prove 4-SAT CNF is NP-complete to the current situation.

Suppose an instance of 4-SAT over variables $$x_1,x_2,\cdots, x_m$$ is given as a boolean formula $$f=c_1\land c_2\land \cdots\land c_m,$$ where $$c_i$$ is a disjunction that has exactly 4 literals for all $$i$$.

Introduce a new variable $$s$$. Suppose $$c_i=w\lor x \lor y \lor z$$ for some literal $$w,x,y,z$$. Let \begin{aligned} c_{i+}&=w\lor x \lor y \lor z\lor s\\ c_{i-}&=w\lor x \lor y \lor z\lor \neg s. \end{aligned}

• If $$c_i$$ can be satisfied by an assignment, then $$c_{i+}\land c_{i-}$$ is satisfied by the same assignment plus $$s=0$$ (or $$s=1$$).
• If $$c_{i+}\land c_{i-}$$ can be satisfied by an assignment, the same assignment without considering $$s$$ must satisfy $$c_i$$ since one of $$s$$ and $$\neg s$$ must be false.

Construct an instance of 5-SAT over variables $$x_1,x_2,\cdots, x_m, s$$, $$g=c_{1+}\land c_{1-}\land c_{2+}\land c_{2-}\land\cdots\land c_{m+}\land c_{m-}.$$

Because of the relation between $$c_i$$ and $$c_{i+}\land c_{i-}$$,

• If $$f$$ is satisfied by an assignment, then $$g$$ is satisfied by the same assignment plus $$s=0$$.
• Conversely, if $$g$$ is satisfied by an assignment, then $$f$$ is satisfied by the same assignment without considering $$s$$.

The above means the transformation from $$f$$ to $$g$$ is a reduction from 4-SAT to 5-SAT. It runs in polynomial time.

For simplicity of explanation, the above restricts $$k$$-SAT to CNF formulas with exactly $$k$$ literals without duplicates. Thanks to a similar simple padding technique, it is does not matter to the construction of reduction above whether we allow at most $$k$$ literals with or without duplicates when we define $$k$$-SAT.

• very nice answer, Thank you very much! – samTT May 22 at 11:38
• @samTT, welcome. – Apass.Jack May 22 at 13:12

Since you did not specify exactly the two languages, let us suppose that 4-SAT is a CNF of this type: (A ∨ B ∨ C ∨ D) ∧ (A¯ ∨ C¯ ∨ F ∨ S) ∧ (E ∨ G ∨ H¯ ∨ Q) ∧ .... A way to reduce this instance of k-SAT into an instance of (k+1)-SAT is this: you can add inside every clause a further literal (for example Z) so the first clause will become (A ∨ B ∨ C ∨ D ∨ Z), the second clause will become (A¯ ∨ C¯ ∨ F ∨ S ∨ Z), the third clause will become (E ∨ G ∨ H¯ ∨ Q ∨ Z) and so on. It is easy to observe that by assigning the value 0 to the variable Z, you get an instance of 5-SAT which is verified if and only if the starting 4-SAT instance is verified.

• You cannot assign a value to a variable &mdash; that's not how you specify a $k$-SAT instance. – Yuval Filmus May 21 at 14:53
• @Yuval Filmus you are right, i meant that the adding of Z to every clause is trivial to the satisfabiality of the problem. – Yamar69 May 21 at 16:58