NP Completeness Lecture Series

Authors
Date November 29th, 2021
Venue CSE 431 Algorithm Engineering at Michigan State University

Intuition-first talks introducing & defining complexity classes, covering the construction & interpretation of reductions with help a sandwich-making robot, outlining the Cooke-Levin theorem via the shenanigans of a certain Doge Jr. picking a SAT lock to get out of doing his NP homework, and unpacking a literal barrel of monkeys (TM) to explore the P ?= NP question.

Supporting Materials