Weeks 12–14 · Sipser 7.2–7.5 · Part IV
NP is not "not polynomial". It is the class of problems where a solution can be checked quickly — and the open question is whether checking quickly implies finding quickly. On this page you can feel the gap: the checker never takes longer than a blink, and the search does.
Type an assignment — x1=1 x2=0 x3=1, or
just 101 in variable order. This is the verifier from Definition 7.19, and it
runs in time linear in the formula.
Random 3-CNF at the hard ratio m ≈ 4.26n, solved by exhaustive search. Each extra variable doubles the work; the verifier for the same instances stays flat.
One node per literal occurrence. Two nodes are joined when they are in different clauses and do not contradict each other. The formula is satisfiable exactly when the graph has a clique of size k = the number of clauses.
One clause per line. ~ or - negates. Variable names
are whatever you write.
To show B is NP-hard you reduce a known hard problem to B: 3SAT ≤ₚ B. Writing B ≤ₚ 3SAT proves that B is easy — it is in NP, which you already knew.
Every year this is the single most expensive error on the final. Say it out loud: A ≤ₚ B means B is at least as hard as A.
Knowing your problem is NP-complete is not the end of the engineering; it is the start of it. It tells you to stop hunting for a clever exact polynomial algorithm, and to reach instead for the machinery that exists precisely because SAT is universal: a SAT or SMT solver, an integer programme, an approximation with a proven ratio, or a parameterised algorithm that is fast when the parameter is small.
Modern solvers routinely dispatch industrial instances with hundreds of thousands of variables — far past anything the brute force on this page could touch — because they exploit structure that random instances do not have. The hardness is worst-case, and your instance is usually not the worst case. Learning to reduce your problem to SAT is the practical skill that Chapter 7 is really teaching.