โ Theory of Computation learning pathTheory of Computation ยท Module 10 of 10
Complexity: P and NP
How hard decidable problems are.
๐ Key ideas
- P: problems solvable in polynomial time by a deterministic TM.
- NP: problems whose solutions can be verified in polynomial time.
- NP-complete problems are in NP and every NP problem reduces to them: SAT, 3-SAT, vertex cover, travelling salesman (decision version).
- Cook-Levin theorem: SAT is NP-complete.
- Whether P = NP is the most famous open problem in computer science.
๐ก Real-life example: NP is like a jigsaw puzzle: finding the solution may take forever, but checking a finished puzzle is quick.
Class PProblems solvable in polynomial time
Class NPProblems verifiable in polynomial time
NP-completeHardest problems in NP
Cook-Levin theoremSAT is NP-complete