What if P=NP? The world becomes a Utopia. Mathematicians are replaced by efficient theorem- discovering machines. It becomes easy to come up with the simplest theory to explain known data ▣ But at the same time. Many cryptosystems are insecure. 11
What if P = NP? ◼ The world becomes a Utopia. ❑ Mathematicians are replaced by efficient theoremdiscovering machines. ❑ It becomes easy to come up with the simplest theory to explain known data ❑ … ◼ But at the same time, ❑ Many cryptosystems are insecure. 11
Completeness [Cook-Levin]There is a class of NP problems, such that NP solve any of them in polynomial time, →solve all NP problems in polynomial time. 12
Completeness ◼ [Cook-Levin] There is a class of NP problems, such that solve any of them in polynomial time, ⇒ solve all NP problems in polynomial time. NP P 12