[proofplan] We prove NP-completeness by verifying the two required properties. Membership in NP follows because a truth assignment is a polynomial-size certificate and each clause can be evaluated in polynomial time. For NP-hardness, we reduce from the NP-complete problem CNF-SAT, first handling the possible empty-clause case by a fixed unsatisfiable $3$-CNF formula. In the remaining case, we use the standard chain construction that replaces every long clause by equisatisfiable clauses of length three and pads shorter clauses by repeated literals. The construction is local to each nonempty clause, preserves satisfiability in both directions, and increases the total formula size only linearly. [/proofplan] [step:Verify that $3\text{-}\mathrm{SAT}$ belongs to NP] Let $\varphi$ be a Boolean formula in $3$-CNF. A certificate for $\varphi$ is a truth assignment \begin{align*} a: V(\varphi) \to \{0,1\}, \end{align*} where $V(\varphi)$ denotes the finite set of Boolean variables occurring in $\varphi$. Given $a$, a deterministic verifier evaluates each literal, then each clause, and finally the conjunction of all clauses. If $m$ is the number of clauses of $\varphi$, then exactly $3m$ literal occurrences are inspected. Therefore the verification time is polynomial in the input length of $\varphi$. Hence $3\text{-}\mathrm{SAT} \in \mathrm{NP}$. [guided] We first check the definition of membership in $\mathrm{NP}$. For an input formula $\varphi$, the certificate should be short and should allow deterministic verification in polynomial time. The natural certificate is a truth assignment \begin{align*} a: V(\varphi) \to \{0,1\}, \end{align*} where $V(\varphi)$ is the set of variables appearing in $\varphi$. This certificate has length at most linear in the number of variables of $\varphi$, hence polynomial in the input length. To verify it, evaluate every literal under $a$: a positive literal $x$ has value $a(x)$, and a negative literal $\neg x$ has value $1-a(x)$. Then evaluate each clause by Boolean disjunction and evaluate the whole formula by Boolean conjunction. Since a $3$-CNF formula with $m$ clauses has exactly $3m$ literal occurrences, the verifier performs only polynomially many elementary Boolean operations. Therefore $3\text{-}\mathrm{SAT}$ belongs to $\mathrm{NP}$. [/guided] [/step] [step:Define the reduction from CNF-SAT to $3\text{-}\mathrm{SAT}$] Let $\mathrm{CNF}\text{-}\mathrm{SAT}$ denote the decision problem whose inputs are CNF formulas and whose yes-instances are exactly the satisfiable CNF formulas. We use the standard CNF form of the Cook-Levin theorem: $\mathrm{CNF}\text{-}\mathrm{SAT}$ is NP-complete. Let $\psi$ be a CNF formula, meaning a finite conjunction of clauses, where each clause is a finite disjunction of literals and the empty disjunction is allowed and is false under every truth assignment. Write \begin{align*} \psi = C_1 \wedge C_2 \wedge \cdots \wedge C_m, \end{align*} where each $C_i$ is such a clause. We define a map $T$ from CNF formulas to $3$-CNF formulas as follows. If some clause $C_i$ is empty, let $z$ be a fresh Boolean variable and define $T(\psi)$ to be the fixed unsatisfiable $3$-CNF formula \begin{align*} (z \vee z \vee z) \wedge (\neg z \vee \neg z \vee \neg z). \end{align*} This case is total and correct because a CNF formula containing an empty clause is unsatisfiable, while the displayed $3$-CNF formula requires both $z=1$ and $z=0$. For the rest of the construction, assume every clause of $\psi$ is nonempty. We construct $T(\psi)$ by replacing each clause independently. If $C_i = (\ell)$ has one literal, replace it by \begin{align*} (\ell \vee \ell \vee \ell). \end{align*} If $C_i = (\ell_1 \vee \ell_2)$ has two literals, replace it by \begin{align*} (\ell_1 \vee \ell_2 \vee \ell_2). \end{align*} If $C_i = (\ell_1 \vee \ell_2 \vee \ell_3)$ has three literals, leave it unchanged. If $C_i = (\ell_1 \vee \cdots \vee \ell_k)$ has $k > 3$ literals, introduce fresh variables $y_1,\dots,y_{k-3}$ that occur nowhere else in the construction, and replace $C_i$ by the conjunction \begin{align*} (\ell_1 \vee \ell_2 \vee y_1) \wedge \bigwedge_{j=2}^{k-3}(\neg y_{j-1} \vee \ell_{j+1} \vee y_j) \wedge (\neg y_{k-3} \vee \ell_{k-1} \vee \ell_k). \end{align*} When $k=4$, the middle conjunction indexed by $2 \le j \le k-3$ is empty, so the replacement is \begin{align*} (\ell_1 \vee \ell_2 \vee y_1) \wedge (\neg y_1 \vee \ell_3 \vee \ell_4). \end{align*} The formula $T(\psi)$ is the conjunction of all replacements. [/step] [step:Prove that each replacement is satisfiable exactly when the original clause is satisfiable] Clauses of length $1$, $2$, and $3$ are immediate, because repeating a literal does not change the truth value of the disjunction. Now fix a clause \begin{align*} C = (\ell_1 \vee \cdots \vee \ell_k) \end{align*} with $k>3$, and let $R(C)$ denote its replacement. Let $b$ be a truth assignment on the original variables occurring in $C$. First assume that $b$ satisfies $C$. Let $r \in \{1,\dots,k\}$ be an index such that $b(\ell_r)=1$. We extend $b$ to the auxiliary variables $y_1,\dots,y_{k-3}$ as follows. If $r \le 2$, set $y_j=0$ for every $j$. If $3 \le r \le k-2$, set $y_j=1$ for $1 \le j \le r-2$ and set $y_j=0$ for $r-1 \le j \le k-3$. If $r \ge k-1$, set $y_j=1$ for every $j$. In each case, every clause of $R(C)$ is satisfied: clauses before the first occurrence of the true original literal are satisfied by their final auxiliary literal, the clause containing $\ell_r$ is satisfied by $\ell_r$, and clauses after it are satisfied by the negation of the preceding auxiliary literal. Conversely, assume that an extension of $b$ to $y_1,\dots,y_{k-3}$ satisfies $R(C)$. If all original literals $\ell_1,\dots,\ell_k$ were false under $b$, then the first clause would force $y_1=1$. Inductively, for each $j=2,\dots,k-3$, the clause \begin{align*} (\neg y_{j-1} \vee \ell_{j+1} \vee y_j) \end{align*} would force $y_j=1$, because $y_{j-1}=1$ and $\ell_{j+1}$ is false. Thus $y_{k-3}=1$. The final clause \begin{align*} (\neg y_{k-3} \vee \ell_{k-1} \vee \ell_k) \end{align*} would then be false, contradicting the assumption that $R(C)$ is satisfied. Therefore at least one original literal is true, so $C$ is satisfied. [guided] The short-clause replacements are satisfiability-preserving because they do not introduce any new logical condition. If $C=(\ell)$, then $(\ell \vee \ell \vee \ell)$ has the same truth value as $\ell$. If $C=(\ell_1 \vee \ell_2)$, then $(\ell_1 \vee \ell_2 \vee \ell_2)$ has the same truth value as $(\ell_1 \vee \ell_2)$. If $C=(\ell_1 \vee \ell_2 \vee \ell_3)$, no replacement is made, so the truth value is unchanged. The long-clause replacement is designed to record, through the auxiliary variables, whether a true original literal has already appeared. We prove the two directions separately. Let \begin{align*} C = (\ell_1 \vee \cdots \vee \ell_k) \end{align*} be a clause with $k>3$, and let $R(C)$ be the conjunction \begin{align*} (\ell_1 \vee \ell_2 \vee y_1) \wedge \bigwedge_{j=2}^{k-3}(\neg y_{j-1} \vee \ell_{j+1} \vee y_j) \wedge (\neg y_{k-3} \vee \ell_{k-1} \vee \ell_k). \end{align*} Here $y_1,\dots,y_{k-3}$ are fresh variables, meaning they occur in no other replacement. Assume first that an assignment $b$ to the original variables satisfies $C$. Choose an index $r \in \{1,\dots,k\}$ with $b(\ell_r)=1$. We now define values for the auxiliary variables. If the true literal occurs among $\ell_1,\ell_2$, set every $y_j$ equal to $0$. Then the first clause is already true, and every later clause is true because it contains $\neg y_{j-1}$ with $y_{j-1}=0$. If $3 \le r \le k-2$, set \begin{align*} y_j = 1 \quad \text{for } 1 \le j \le r-2, \end{align*} and set \begin{align*} y_j = 0 \quad \text{for } r-1 \le j \le k-3. \end{align*} The clauses before the one containing $\ell_r$ are satisfied by the positive auxiliary literal at the end of the clause. The clause containing $\ell_r$ is satisfied by the original literal $\ell_r$. Every later clause is satisfied by the negated auxiliary literal $\neg y_{j-1}$, because from that point onward the preceding auxiliary variable is set to $0$. If the first true literal is $\ell_{k-1}$ or $\ell_k$, set every $y_j$ equal to $1$. Then all earlier clauses are satisfied by their positive auxiliary literals, and the final clause is satisfied by $\ell_{k-1}$ or $\ell_k$. Thus every satisfying assignment of $C$ extends to a satisfying assignment of $R(C)$. Conversely, suppose some extension of $b$ satisfies $R(C)$. We prove that $C$ must be true. Assume for contradiction that every original literal $\ell_1,\dots,\ell_k$ is false under $b$. Then the first clause \begin{align*} (\ell_1 \vee \ell_2 \vee y_1) \end{align*} can be true only if $y_1=1$. Now suppose $y_{j-1}=1$ for some $j$ with $2 \le j \le k-3$. Since $\ell_{j+1}$ is false, the clause \begin{align*} (\neg y_{j-1} \vee \ell_{j+1} \vee y_j) \end{align*} can be true only if $y_j=1$. By induction, $y_{k-3}=1$. But then the final clause \begin{align*} (\neg y_{k-3} \vee \ell_{k-1} \vee \ell_k) \end{align*} is false, since $y_{k-3}=1$ and both $\ell_{k-1}$ and $\ell_k$ are false. This contradicts the assumption that $R(C)$ is satisfied. Therefore at least one original literal is true, and hence $C$ is satisfied. [/guided] [/step] [step:Show that the construction is a polynomial-time many-one reduction] Let $N$ denote the total number of literal occurrences in $\psi$. If the scan of $\psi$ finds an empty clause, the construction outputs the fixed formula $(z \vee z \vee z) \wedge (\neg z \vee \neg z \vee \neg z)$, which has constant size. Otherwise, a clause of length $k \le 3$ is replaced by one clause of length $3$, and a clause of length $k>3$ is replaced by $k-2$ clauses of length $3$ and introduces $k-3$ fresh variables. Therefore the number of literal occurrences in the replacement of a length-$k$ clause is at most $3(k-2)$ when $k>3$ and at most $3$ when $k \le 3$. Summing over all clauses, the length of $T(\psi)$ is at most linear in $N$. The transformation only scans each literal, writes a constant number of symbols per output literal occurrence, and creates fresh variable names for the auxiliary variables. Hence $\psi \mapsto T(\psi)$ is computable in polynomial time. [/step] [step:Conclude that $3\text{-}\mathrm{SAT}$ is NP-hard and therefore NP-complete] If $\psi$ contains an empty clause, then $\psi$ is unsatisfiable by the definition of the empty disjunction, and $T(\psi)=(z \vee z \vee z) \wedge (\neg z \vee \neg z \vee \neg z)$ is also unsatisfiable because no truth assignment gives both $z=1$ and $z=0$. If $\psi$ has no empty clause, the clause-by-clause equivalence proved above shows that a truth assignment satisfies $\psi$ if and only if it extends to a truth assignment satisfying $T(\psi)$. Hence, in all cases, \begin{align*} \psi \in \mathrm{CNF}\text{-}\mathrm{SAT} \iff T(\psi) \in 3\text{-}\mathrm{SAT}. \end{align*} The map $T$ is computable in polynomial time, so it is a polynomial-time many-one reduction from CNF-SAT to $3\text{-}\mathrm{SAT}$. Since $\mathrm{CNF}\text{-}\mathrm{SAT}$ is NP-complete by the CNF form of the Cook-Levin theorem, this reduction proves that $3\text{-}\mathrm{SAT}$ is NP-hard. Together with $3\text{-}\mathrm{SAT} \in \mathrm{NP}$, proved in the first step, this shows that $3\text{-}\mathrm{SAT}$ is NP-complete. [/step]