โ† Theory of Computation learning path
Theory of Computation ยท Module 10 of 10

Complexity: P and NP

How hard decidable problems are.

๐Ÿ“– Key ideas

  1. P: problems solvable in polynomial time by a deterministic TM.
  2. NP: problems whose solutions can be verified in polynomial time.
  3. NP-complete problems are in NP and every NP problem reduces to them: SAT, 3-SAT, vertex cover, travelling salesman (decision version).
  4. Cook-Levin theorem: SAT is NP-complete.
  5. 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