MIT
Lecture 15: NP-Completeness
Data Science, Analytics & Computer TechnologyComputer ScienceScience & MathMathematicsEngineering
Om kurset
Description: Quickly reviewed last lecture. Covered NP-completeness; \(SAT\) and \(3SAT\); \(3SAT\) ≤\(_P\) \(HAMPATH\); and \(3SAT\) ≤\(_P\) \(CLIQUE\). Discussed a strategy for proving NP-completeness with a reduction from \(3SAT\) by constructing gadgets that simulate variables and clauses. Instructor: Prof. Michael Sipser