Skip to content
TheChatArchiveThe Chat Archive
GPT 5.1 Codex Max· openaiHugging Face Frontier Reasoning Traces

Prove 3-SAT is NP-complete. Show it's in NP then construct a polynomial-time reduction…

  1. User

    Prove 3-SAT is NP-complete. Show it's in NP then construct a polynomial-time reduction from SAT to 3-SAT converting clauses with more than 3 literals using new variables.

  2. Assistant

    Outlining standard 3-SAT NP-completeness proof

    The full reduction from SAT to 3-SAT is confirmed with the known clause-splitting chain gadget for clauses longer than 3 literals and straightforward padding of 1- and 2-literal clauses using dummy or repeated literals. This ensures an equisatisfiable 3-CNF formula constructed in polynomial time, completing the NP-hardness argument alongside the obvious NP membership. Let's start by clarifying what 3-SAT is: it’s the problem of determining whether a Boolean formula in conjunctive normal form (CNF) is satisfiable when each clause has exactly three literals (variables or their negations). Our goal is to prove that this problem is NP-complete. There are two steps:

    1. Show 3-SAT is in NP. This is straightforward. Given a formula in 3-CNF and a purported assignment of truth values to the variables, you can check in polynomial time whether every clause has at least one true literal. Because verifying a solution can be done efficiently, 3-SAT is in NP.

    2. Show 3-SAT is NP-hard by reducing the general SAT problem to it. Recall that SAT is NP-complete, so if we can transform any SAT instance into an equivalent 3-SAT instance in polynomial time, that proves 3-SAT is NP-hard.

      Here’s the standard reduction: take an arbitrary CNF formula, which may have clauses longer than three literals, and convert each clause into an equivalent conjunction of clauses each with exactly three literals. If a clause has fewer than three literals, you can pad it: for a single literal (l), replace it with the clause ((l \lor x \lor \neg x)) for a fresh variable (x); for two literals (l_1 \lor l_2), use ((l_1 \lor l_2 \lor x)) AND ((l_1 \lor l_2 \lor \neg x)), which forces (l_1 \lor l_2) to be true regardless of (x).

      For a clause (C = (l_1 \lor l_2 \lor \dots \lor l_k)) with (k > 3), introduce new variables (y_1, y_2, \dots, y_{k-3}) and replace (C) by the conjunction [ (l_1 \lor l_2 \lor y_1)\ \wedge\ (\neg y_1 \lor l_3 \lor y_2)\ \wedge\ (\neg y_2 \lor l_4 \lor y_3)\ \wedge\ \dots\ \wedge\ (\neg y_{k-3} \lor l_{k-1} \lor l_k). ] This chain of 3-clauses is satisfiable if and only if the original clause (C) is satisfiable: intuitively, if none of the (l_i) is true you are forced to set all the (y_j) to true, which makes the last clause false; conversely, if some (l_i) is true, you can set the (y_j) to make all the new clauses true. Doing this for every long clause yields a 3-CNF formula that is satisfiable exactly when the original formula is satisfiable. The size of the new formula is only polynomially larger than the original.

      This transformation runs in polynomial time, so it’s a valid reduction from SAT to 3-SAT.

    Since 3-SAT is in NP and SAT ≤ₚ 3-SAT, we conclude that 3-SAT is NP-complete.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.