A student claims: 'Since 3-SAT only allows clauses with exactly 3 literals, it must be an easier special case of SAT — fewer choices per clause means fewer cases to check.' Which response is most accurate?
AThe student is correct; restricting clause length to 3 places 3-SAT in a tractable subclass of SAT
BThe student is incorrect; 3-SAT is NP-complete, meaning it is as hard as the general SAT problem despite (and in a sense because of) its restricted form
CThe student is partially correct; 3-SAT is NP-complete but is computationally easier than SAT in practice
DThe student is correct for formulas with few variables, but 3-SAT becomes hard as variable count grows
3-SAT is NP-complete — it is computationally equivalent in difficulty to general SAT and to every other NP-complete problem. The restriction to exactly 3 literals per clause does not make the problem easier because the *combinatorial interaction* between clauses through shared variables is what drives the hardness, and this interaction survives the syntactic restriction. In fact, 2-SAT (clauses with at most 2 literals) IS solvable in polynomial time — the hardness emerges specifically at 3 literals, making the 3-SAT threshold a sharp phase transition in the theory of boolean satisfiability.
Question 2 Multiple Choice
When proving a new graph problem is NP-hard, researchers almost always reduce FROM 3-SAT rather than from general SAT or other NP-complete problems. What is the primary reason for this preference?
A3-SAT is strictly harder than general SAT, making reductions from 3-SAT more powerful
B3-SAT's uniform clause structure (exactly 3 literals per clause) maps cleanly onto combinatorial gadgets in graph constructions, making reductions easier to design and verify
CGeneral SAT cannot be reduced to graph problems, but 3-SAT can because of its restricted form
DReductions from 3-SAT are preferred because 3-SAT has fewer satisfying assignments, simplifying the case analysis
3-SAT and general SAT are computationally equivalent (both NP-complete), so the preference for 3-SAT as a reduction source is not about strength but about structure. A 3-SAT clause is a clean, uniform object: exactly 3 variables, each possibly negated, one constraint (at least one literal true). This uniformity makes it natural to design 'clause gadgets' and 'variable gadgets' in graph constructions: each clause becomes one subgraph, each variable becomes another, and they connect through shared nodes. General SAT clauses of varying sizes complicate this mapping. The regularity of 3-SAT is precisely what makes it so valuable as a reduction tool.
Question 3 True / False
Converting a general CNF formula into a 3-SAT instance using auxiliary variables may change whether the formula is satisfiable, so the conversion is mainly an approximation and not a true polynomial reduction.
TTrue
FFalse
Answer: False
The conversion from general CNF to 3-CNF using auxiliary variables is an exact, satisfiability-preserving transformation, not an approximation. For example, a 4-literal clause (a ∨ b ∨ c ∨ d) becomes (a ∨ b ∨ y) ∧ (¬y ∨ c ∨ d) using a fresh auxiliary variable y. The resulting 3-CNF formula is satisfiable if and only if the original formula is satisfiable. Short clauses can be padded with repeated literals (e.g., (a ∨ b) becomes (a ∨ b ∨ b)). The entire conversion runs in polynomial time. These properties — polynomial time and preserved satisfiability — are exactly what make it a valid polynomial-time reduction.
Question 4 True / False
Given a 3-SAT instance and a proposed variable assignment, it is possible to verify whether the assignment satisfies the formula in polynomial time — specifically, linear time in the size of the formula.
TTrue
FFalse
Answer: True
This is why 3-SAT is in NP. Verification is simple: for each clause, check whether at least one of its three literals is made true by the assignment. With k clauses and n variables, this takes O(k) time — linear and clearly polynomial. The hardness of 3-SAT is not about verification (checking a solution is easy) but about *finding* a satisfying assignment (or proving none exists) without a certificate. This asymmetry between easy verification and hard search is the defining characteristic of NP-complete problems.
Question 5 Short Answer
Explain why 3-SAT's NP-completeness is described as a 'robustness' result. What does it reveal about the nature of computational hardness that a problem remains NP-complete even when its structure is restricted to clauses of exactly 3 literals?
Think about your answer, then reveal below.
Model answer: A robustness result shows that hardness is not an artifact of a problem's messiness or generality — it survives even after imposing clean, highly structured constraints. General SAT allows clauses of any size, which might seem necessary for hardness. The fact that restricting every clause to exactly 3 literals preserves NP-completeness reveals that the difficulty is intrinsic to the Boolean constraint-satisfaction structure, not a feature of syntactic complexity. Practically, this means the hardness cannot be 'designed away' by simplifying the problem structure. Theoretically, it explains why 3-SAT is so useful as a reduction source: its regularity makes reductions easier to construct and its hardness guarantees the target problem is genuinely hard. The NP-completeness of 3-SAT is part of the deeper insight that many combinatorially simple-looking problems are computationally intractable.
The contrast with 2-SAT is instructive: 2-SAT (clauses with at most 2 literals) is solvable in polynomial time via implication graphs. The transition from 2 to 3 literals is the exact point where polynomial-time algorithms give way to apparent intractability. This phase transition — from easy to NP-complete with a single literal added per clause — is one of the most striking results in computational complexity theory.