3-SAT as a Decision Problem
Many NP-hardness proofs begin with a problem already known to be NP-complete and transform its instances into instances of a new problem. 3-SAT is one of the standard starting problems for this purpose. To use it correctly, we need to specify exactly what its instances are, what counts as a yes-answer, and why a proposed solution can be checked efficiently.
Throughout, a Boolean variable takes one of the two values \(0\) (false) and \(1\) (true). A literal is either a variable \(x\), called a positive literal, or its negation \(\neg x\), called a negative literal. An assignment gives a value to every variable. Under an assignment, \(x\) has the assigned value and \(\neg x\) has the opposite value.
For example, \((x\vee \neg y\vee z)\) is one clause, while \((x\vee \neg y\vee z)\wedge(\neg x\vee y\vee z)\) is a formula with two clauses. An instance is the formula; a yes-answer means that at least one assignment satisfies all its clauses. Different assignments may satisfy the same instance.
Some presentations allow clauses with one, two, or three literals, rather than exactly three. These conventions give equivalent decision problems: repeating a literal in a disjunction does not change its truth value. The next result makes that conversion precise, including the possibility of an empty clause under the at-most-three convention.
Proof. For a nonempty clause \(C=(\ell_1\vee\cdots\vee\ell_k)\) with \(1\le k\le3\), repeat its last literal until there are three positions. For instance, \((a\vee b)\) becomes \((a\vee b\vee b)\), and \((c)\) becomes \((c\vee c\vee c)\). Under any assignment, a disjunction is true exactly when at least one of its original literals is true. Repeating a literal creates no new way for the disjunction to become true or false, so each replacement preserves the clause's truth value for every assignment. If an empty clause is permitted, it is false under every assignment. Replace it by \((x\vee x\vee x)\wedge(\neg x\vee\neg x\vee\neg x)\), using a variable \(x\). The first clause requires \(x=1\) and the second requires \(x=0\), so their conjunction is unsatisfiable, just like the empty clause. Thus the whole formula has the same satisfiability status after replacement. \(\square\)
Evaluating a Formula
Worked Example: Checking a Satisfying Assignment
Consider the formula on variables \(x,y,z\):
Test the assignment \(x=0,\ y=0,\ z=0\). In the first clause, the literal values are \(x=0,\ \neg y=1,\ z=0\), so the clause value is \(0\vee1\vee0=1\). In the second, the values are \(\neg x=1,\ y=0,\ z=0\), giving \(1\vee0\vee0=1\). In the third, they are \(x=0,\ y=0,\ \neg z=1\), giving \(0\vee0\vee1=1\). The formula value is therefore \(1\wedge1\wedge1=1\), so this assignment satisfies \(F\).
Check: Substituting the assignment directly gives \(F=(0\vee1\vee0)\wedge(1\vee0\vee0)\wedge(0\vee0\vee1)=1\wedge1\wedge1=1\). Each clause has exactly one true literal here, which is enough for satisfaction.
A candidate assignment is a certificate for a yes-instance. The verifier does not need to search among all assignments: it evaluates the three literals in each clause and checks that every clause has at least one true literal. The following example records that check explicitly.
Worked Example: Repeated Literals and Clause-by-Clause Verification
Let
and test \(p=0,\ q=1,\ r=0\). The first clause has values \(p=0,\ p=0,\ q=1\), so it evaluates to \(0\vee0\vee1=1\). The second has values \(\neg p=1,\ r=0,\ r=0\), so it evaluates to \(1\vee0\vee0=1\). The third has values \(\neg q=0,\ \neg r=1,\ p=0\), so it evaluates to \(0\vee1\vee0=1\). Hence \(H=1\wedge1\wedge1=1\), and the assignment satisfies \(H\).
Check: The repeated occurrences of \(p\) and \(r\) are counted as separate positions, but they have the same value each time. The three computed clause values are \(1,1,1\); their conjunction is \(1\), as required.
To prove that a formula is unsatisfiable, checking one failed assignment is not enough: a different assignment might satisfy it. The next example arranges clauses so that every possible assignment fails a clause.
Worked Example: An Unsatisfiable Formula
For each assignment to \(x,y,z\), form a clause whose three literals are all false on that assignment. Their conjunction is
Here is the full check. In each row, the listed clause is false on the corresponding assignment because all three of its literals have value \(0\).
| Assignment \((x,y,z)\) | Clause false on that assignment | Literal values |
|---|---|---|
| \((0,0,0)\) | \((x\vee y\vee z)\) | \((0,0,0)\) |
| \((0,0,1)\) | \((x\vee y\vee\neg z)\) | \((0,0,0)\) |
| \((0,1,0)\) | \((x\vee\neg y\vee z)\) | \((0,0,0)\) |
| \((0,1,1)\) | \((x\vee\neg y\vee\neg z)\) | \((0,0,0)\) |
| \((1,0,0)\) | \((\neg x\vee y\vee z)\) | \((0,0,0)\) |
| \((1,0,1)\) | \((\neg x\vee y\vee\neg z)\) | \((0,0,0)\) |
| \((1,1,0)\) | \((\neg x\vee\neg y\vee z)\) | \((0,0,0)\) |
| \((1,1,1)\) | \((\neg x\vee\neg y\vee\neg z)\) | \((0,0,0)\) |
There are \(2^3=8\) assignments and eight rows, one for each assignment. Every assignment makes at least one clause false, so none satisfies the conjunction. Thus \(U\) is a no-instance of 3-SAT.
Check: For any assignment, choose the clause whose positive or negative literal for each variable is false at that variable's assigned value. That clause appears in the displayed list and is false. This verifies the conclusion for all assignments, not just a sample.
Why 3-SAT Is in NP
Proof. Take a well-formed formula as input. A certificate lists one Boolean value for each variable occurring in the formula. The number of such variables is at most the formula's encoding length, since each occurring variable must be represented in the input. The verifier scans each clause, reads the three assigned literal values, reverses a value when the literal is negated, and accepts the clause if at least one of the three values is \(1\). It accepts the certificate exactly when it accepts every clause. Each input position and each clause need only be processed a bounded number of times, so the total work is polynomial in the input length. If the verifier accepts, every clause is true under the listed assignment, which is precisely the definition of a satisfying assignment. Conversely, if the formula is satisfiable, listing a satisfying assignment makes the verifier accept. Thus the certificates characterize exactly the yes-instances, and verification is polynomial-time. \(\square\)
The empty conjunction, if allowed as an input, is true under every assignment and can be verified by the empty assignment; a formula with no variables and at least one three-literal clause cannot arise under the usual requirement that each literal names a variable. Malformed encodings are rejected during parsing. These conventions do not affect the polynomial verification argument.
The NP-Completeness Theorem
The membership part has just been proved. The NP-hardness part says that every problem in NP can be translated, in polynomial time, into a 3-SAT instance so that the original instance is a yes-instance exactly when the resulting formula is satisfiable. This is a standard foundational theorem of complexity theory. Its hardness proof is beyond this tutorial; it is used here as a starting theorem rather than derived from scratch.
In applications, the important direction is from a known NP-complete problem to the target problem. If a later reduction transforms a 3-SAT formula into an instance of a graph decision problem and preserves yes-answers in both directions, then the graph problem is NP-hard. To conclude NP-completeness, one also needs to establish that the graph problem belongs to NP. The theorem makes 3-SAT a source problem: its role is to supply a well-understood hard decision problem, not to provide an assignment by itself.
Common Pitfall: What “Three” Counts
Wrong interpretation: “3-SAT means a formula has exactly three clauses.” That is not the definition. The number three refers to the number of literal positions in each clause. For instance, \(F=(a\vee b\vee c)\) has one clause but is a valid 3-SAT instance; \((a\vee b)\wedge(c\vee d)\wedge(e\vee f)\) has three clauses but is not an exactly-three-literal instance because each clause has only two literal positions.
Correction: Check each clause separately. In the first formula, its single clause has three literals, so it is in 3-CNF. In the second, there are three clauses, but each contains two literals. Under the at-most-three convention it is permitted; to use the exactly-three convention, replace each clause by a repeated-literal version, such as \((a\vee b\vee b)\). The issue is the width of each clause, not the total number of clauses.
A second frequent error is to require all three literals in a clause to be true. The clause is an OR, so one true literal suffices. In the first worked example, every clause had exactly one true literal and the whole formula was still satisfied.
Check Your Understanding
For each question, identify the formula or assignment precisely before drawing a conclusion.
- For \(F=(x\vee\neg y\vee z)\wedge(\neg x\vee y\vee z)\), evaluate \(F\) at \(x=1,\ y=1,\ z=0\) by computing each clause value.
- Convert \((a\vee\neg b)\wedge(c)\) to exactly-three-literal clauses without changing its truth value under any assignment.
- Explain why a satisfying assignment is a certificate for a yes-instance of 3-SAT, but a single nonsatisfying assignment does not certify a no-instance.
- State both requirements in the definition of NP-completeness and identify which one follows from the verifier proposition.
- For each assignment to \(p,q\), identify a clause false on it among \((p\vee q\vee q)\), \((p\vee\neg q\vee\neg q)\), \((\neg p\vee q\vee\neg q)\), and \((\neg p\vee\neg q\vee\neg q)\). Is the conjunction satisfiable?