A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
3-SAT restricts SAT to formulas in conjunctive normal form with exactly 3 literals per clause. Despite this restriction, 3-SAT remains NP-complete and is the most common source for polynomial-time reductions proving other problems NP-complete. It provides a practical template for constructing hardness proofs across scheduling, graph algorithms, and optimization problems.
Work through classic 3-SAT reductions (CLIQUE, VERTEX-COVER, INDEPENDENT-SET). Build a reduction from vertex cover to 3-SAT yourself.
You already know SAT is NP-complete. 3-SAT is SAT with a particular syntactic restriction: the formula must be in conjunctive normal form (a conjunction of clauses) and every clause must contain exactly three literals. The first thing to verify is that this restriction does not reduce the difficulty — and it does not. Every SAT instance can be converted to 3-SAT in polynomial time by splitting large clauses (introducing auxiliary variables) and padding short ones. So 3-SAT is also NP-complete. The restriction turns out to be practically useful: the rigid three-literal structure makes it easier to construct reductions to other problems, because you can build small gadgets that exploit the constraint directly.
A polynomial-time reduction from 3-SAT to a problem X is a function f, computable in polynomial time, that maps 3-SAT instances to instances of X such that: the 3-SAT formula is satisfiable if and only if f(φ) is a yes-instance of X. This proves X is NP-hard. The art is in designing f — typically by constructing gadgets, small substructures in X's domain (graph edges, schedule slots, etc.) that mimic the role of variables and clauses in 3-SAT. The reduction direction is crucial: you go *from* 3-SAT *to* X. If you could solve X efficiently, you could solve 3-SAT efficiently (by applying f and then calling your solver for X), which would make 3-SAT tractable — but it is NP-hard, so X must also be hard.
A classic example is the reduction from 3-SAT to INDEPENDENT SET: given a formula with k clauses, construct a graph with 3k nodes (one per literal occurrence) connected by two types of edges — within each clause's triangle (forcing exactly one literal from each clause to be chosen) and between opposite literals x and ¬x (preventing contradictory assignments). An independent set of size k exists if and only if the formula is satisfiable. The independent set "is" a satisfying assignment, encoded spatially. The same structural idea recurs across different reductions: variables become choices, clauses become constraints, and the graph or schedule enforces consistency.
What makes 3-SAT the standard source for hardness proofs — rather than general SAT or some other NP-complete problem — is a combination of rigidity and tractability of the reduction machinery. The three-literal structure is rich enough to simulate arbitrary Boolean constraints but constrained enough that gadgets can be small and explicit. When you encounter a new combinatorial problem and want to show it is NP-hard, the standard approach is: (1) show it is in NP, (2) identify a structural analogy between your problem's constraints and 3-SAT clauses, (3) build gadgets that translate clauses and variables, and (4) verify that the mapping is polynomial and that satisfiability is preserved in both directions. Mastering this template unlocks the ability to prove hardness for scheduling, coloring, packing, and hundreds of other problems.