MIT

Lecture 16: Cook-Levin Theorem

Data Science, Analytics & Computer TechnologyComputer ScienceScience & MathMathematicsEngineering

Om kurset

Description: Quickly reviewed last lecture. Proved Cook-Levin Theorem: \(SAT\) is NP-complete. Also proved \(3SAT\) is NP-complete. Instructor: Prof. Michael Sipser