NP-Complete
Kent Quanrud · 78:22 · Watch on YouTube
This lecture shows that 3-coloring is as hard as 3-SAT, then argues that every polynomial-time-checkable search problem is equivalent to the others: one polynomial-time algorithm for any of them would solve them all....