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
Reduction and completeness Decision problem for language A is reducible to that for language B in time t if 3f:Domain(A)> Domain(B)s.t.V input instance x for A, 1.x∈A台f(x)∈B,and 2. one can compute f(x)in time t(x) Thus to solve A,it is enough to solve B. ▣First compute f(x) Run algorithm for B on f(x). ▣If the algorithm outputs f(x)∈B,then output x∈A. 13
Reduction and completeness ◼ Decision problem for language 𝐴 is reducible to that for language 𝐵 in time 𝑡 if ∃𝑓:𝐷𝑜𝑚𝑎𝑖𝑛 𝐴 → 𝐷𝑜𝑚𝑎𝑖𝑛(𝐵) s.t. ∀ input instance 𝑥 for 𝐴, 1. 𝑥 ∈ 𝐴 ⇔ 𝑓 𝑥 ∈ 𝐵, and 2. one can compute 𝑓(𝑥) in time 𝑡 𝑥 ◼ Thus to solve 𝐴, it is enough to solve 𝐵. ❑ First compute 𝑓(𝑥) ❑ Run algorithm for 𝐵 on 𝑓(𝑥). ❑ If the algorithm outputs 𝑓 𝑥 ∈ 𝐵, then output 𝑥 ∈ 𝐴. 13
NP-completeness NP-completeness:A language L is NP- complete if OL∈NP VL'E NP,L'is reducible to L in polynomial time. ■ Such problems L are the hardest in NP. Once you can solve L,you can solve any other problem in NP. NP-hard:any NP language can reduce to it. i.e.satisfies 2nd condition in NP-completeness def. 14
NP-completeness ◼ NP-completeness: A language 𝐿 is NPcomplete if ❑ 𝐿 ∈ 𝐍𝐏 ❑ ∀𝐿 ′ ∈ 𝐍𝐏, 𝐿 ′ is reducible to 𝐿 in polynomial time. ◼ Such problems 𝐿 are the hardest in NP. ◼ Once you can solve 𝐿, you can solve any other problem in NP. ◼ NP-hard: any NP language can reduce to it. ❑ i.e. satisfies 2nd condition in NP-completeness def. 14
Completeness NP- The hardest problems in NP. Complete ■Cook-Lein:SAT. Karp:21 other problems such as TSP are also NP-complete NP Later:thousands of NP- complete problems from various sciences. 15
Completeness ◼ The hardest problems in NP. ◼ Cook-Levin: SAT. ◼ Karp: 21 other problems such as TSP are also NP-complete ◼ Later: thousands of NPcomplete problems from various sciences. NP P NPComplete 15