Soptq

To read this article, it is necessary to understand that the SAT problem is NP-complete, which is mainly proven by the Cook-Levin theorem. There are many excellent resources that have proven the NP-completeness of SAT, but I will omit them here, please refer to them yourself. If I have time in the future, I will add a proof of the SAT problem as I understand it.

The description of 3-SAT (3-CNF-SAT) is: Determine whether there exists a Boolean expression $C = C_1 \cap C_2 \cap \cdots \cap C_n$, where $C_i = x_a \cup x_b \cup x_c$, such that $C = 1$. That is, determine whether there exists a Boolean expression $C = (x_a^1 \cup x_b^1 \cup x_c^1)\cap (x_a^2 \cup x_b^2 \cup x_c^2)\cap \cdots\cap (x_a^n \cup x_b^n \cup x_c^n)$ that is true.

To prove the NP-completeness of 3-SAT, we need to 1) prove that it is an NP problem. 2) prove that it is NP-hard. 3-SAT is similar to the SAT problem, and when we obtain a set of solutions, we only need to substitute them into the Boolean expression to determine the correctness of the solution. So 3-SAT is obviously an NP problem. To prove its NP-hardness, we will reduce SAT to 3-SAT.

For each SAT problem, for example:

$\begin{cases} C = C_1 \cap C_2 \cap \cdots \cap C_n \\ C_i = x_a^i \cup x_b^i \cup \cdots \cup x_m^i \end{cases}$

Each $C_i$ consists of a certain number of variables. We will perform the following operations on each group of variables.

• If $\lvert C_i \rvert = 1$, that is, only one variable is involved in the composition of $C_i$, for example, $C_i = x_a^i$. We transform it into $C_i = x_a^i \cup x_a^i \cup x_a^i$.
• If $\lvert C_i \rvert = 2$, for example, $C_i = x_a^i \cup x_b^i$. We transform it into $C_i = x_a^i \cup x_a^i \cup x_b^i$.
• If $\lvert C_i \rvert = 3$, we keep it unchanged.
• If $\lvert C_i \rvert = 4$, for example, $C_i = x_a^i \cup x_b^i \cup x_c^i \cup x_d^i$. We transform it into $C_i = (x_a^i \cup x_b^i \cup w^i)$ $\cap ( \overline{w^i} \cup x_c^i \cup x_d^i)$. Where $w^i$ is a new variable.
• And so on.

The above operations can obviously be done in polynomial time. Therefore, given a SAT problem, we can convert it to a 3-SAT problem in polynomial time. And when SAT has a solution, 3-SAT must also have a solution; and when 3-SAT has a solution, since 3-SAT is a subclass of SAT, SAT also has a solution. Therefore, 3-SAT is NP-complete.