SAT (Fundamental algorithms, Spring 2023, Lecture 9)
Kent Quanrud · 68:02
This lecture introduces Boolean satisfiability as a simple-looking search problem whose polynomial-time status is unknown, then shows why restricting the input (CNF, 3-SAT, circuits) does not make it easier: size-pres...