Chapter 11 · Limitations of Algorithm Power

P vs NP Lab

Finding a satisfying assignment for a Conjunctive Normal Form (CNF) formula may take 2ⁿ tries — but checking one proposed answer takes a single pass. That gap between solving and verifying is what P vs NP — deterministic Polynomial time (P) versus Nondeterministic Polynomial time (NP) — is about.

variable = 1 true literal / satisfied clause / satisfying assignment false clause / failed assignment assignment being checked
Why 2ⁿ hurts

The map: P ⊆ NP, NP-complete, NP-hard

Click a region. This is the picture if P ≠ NP (what most researchers believe). P ⊆ NP is proven: a problem you can solve fast, you can certainly check fast.

Definitions. P: solvable in polynomial time. NP: a proposed solution (certificate) can be checked in polynomial time. NP-hard: every NP problem reduces to it in polynomial time. NP-complete = in NP and NP-hard. Click a region for examples.

🤔 Practice: which diagrams do not contradict current knowledge?

Mark each picture of P, NP and NPC (the NP-complete problems) as consistent or contradicting, then check. (Levitin Exercise 11.3.11.)

A reduction you can click: Vertex Cover ⇔ Clique

Click vertices in either graph to put them in W (a candidate vertex cover of G). The right graph is the complement Ḡ (edges exactly where G has none) and highlights V − W.

G — vertex cover W

Complement Ḡ — clique V − W

in W (left) in V − W (right) covered edge / clique edge uncovered edge / missing clique pair (the same pairs!)

How to read this

  • A CNF formula is an AND of clauses; each clause is an OR of literals (a variable or its negation). It is satisfiable if some 0/1 assignment makes every clause true.
  • In a clause box, green literals are true under the current assignment; checking stops at the first true literal (a clause needs just one).
  • The grid has one cell per assignment, in binary order 00…0 to 11…1. Brute force colors them one by one; “guess then check” lights up a single cell.
  • Counters count literal checks — the basic operation. Brute force: up to 2ⁿ × (formula length). Verifying: at most the formula length.
  • In the reduction, red edges on the left and red pairs on the right are always the same pairs — that is the whole proof.

Try this

  1. Worked-example formula, brute force: 32 assignments, 12 satisfy it. Now tick “stop at the first” — assignment #9 (A=0 B=1 C=0 D=0 E=0) is the first hit.
  2. Switch to “guess, then check” and press Lucky guess: 4 clause checks and done. Flip D to 1 — which clause rejects it now?
  3. Load the unsatisfiable example. Why can a verifier never convince you of a “no” answer with one certificate, while brute force can?
  4. Load the 8-variable example: only 2 of the 256 assignments work, and the first is #155. A verifier handed that one certificate needs just 23 clause checks. Each extra variable doubles the grid — see the table: at n = 64 brute force needs centuries.
  5. Reduction: find a cover of size 3 in G (hint: vertex 1 plus two more). The complement then shows a clique of size 6 − 3 = 3.

Go deeper

📖 Lesson 11: Limitations of Algorithm Power 🏟️ Arena · Chapter 11 🧩 sat-verify 🧩 sat-brute-force 🧩 vertex-cover-verify 🧩 clique-verify 🧩 subset-sum-to-partition-reduction 🎮 Decision trees & lower bounds 🎮 Backtracking (coping with NP-hardness)

Reference: Levitin §11.3. Cook's theorem (1971): CNF satisfiability (CNF-SAT) is NP-complete. Other NP-complete problems follow by polynomial-time reductions, e.g. 3-SAT → Vertex Cover → Clique.