title: "Lecture 14 - NP and Polynomial-Time Verifiers"
unit: 3
lecture: 14

Lecture 14 - NP and Polynomial-Time Verifiers

(Skeleton for Fall 2026.)

Verifiers

TODO: verifier definition with certificates (drill it, quantifiers spelled out: there exists a certificate the verifier accepts in polynomial time); verifying is easier than solving.

NP, Two Equivalent Definitions

TODO: verifier definition and nondeterministic-TM definition, proved equivalent; example problems (HAMPATH, CLIQUE, SUBSET-SUM, SAT).

P versus NP

TODO: what the question actually asks; why we believe P is not NP; what a proof either way would mean; the million-dollar framing done honestly.