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.

  • 2
    $\begingroup$ Can you define your version of $k$-SAT? $\endgroup$ – Yuval Filmus May 21 '19 at 10:29
  • $\begingroup$ k-SAT = { F | F is a satisfiable Boolean formula in k-CNF } $\endgroup$ – samTT May 21 '19 at 10:31
  • 2
    $\begingroup$ What’s $k$-CNF for you? $\endgroup$ – Yuval Filmus May 21 '19 at 10:57
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 21 '19 at 14:54
  • 1
    $\begingroup$ To make @YuvalFilmus's question more specific, does "$k$-CNF" mean that each clause has at most $k$ literals, or exactly $k$ literals? $\endgroup$ – David Richerby May 21 '19 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.

  • $\begingroup$ very nice answer, Thank you very much! $\endgroup$ – samTT May 22 '19 at 11:38
  • $\begingroup$ @samTT, welcome. $\endgroup$ – John L. May 22 '19 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.