Boolean satisfiability
Kent Quanrud · 60:31
Boolean SAT, CNF-SAT, 3-SAT, and Circuit SAT are polynomial-time equivalent: a poly-time solver for any one of them yields a poly-time solver for the others. The lecture shows this by constructing small, efficient con...