CMPS130: Overview of complexity classes, Part 2
C. Seshadhri · 9:47
The lecture defines NP via polynomial-size certificates and a deterministic verifier, presents SAT as the canonical NP problem (and the intended NP-complete example), then starts a Venn-diagram picture of P / NP / NP-...