Examples of NP problems Factoring:factor a given number n. Decision version:Given (n,k),decide whether n has a factor less than k. Factoring is in NP:For any candidate factor m <k,it's easy to check whether mn. 6
Examples of NP problems ◼ Factoring: factor a given number 𝑛. ◼ Decision version: Given (𝑛, 𝑘), decide whether 𝑛 has a factor less than 𝑘. ◼ Factoring is in NP: For any candidate factor 𝑚 ≤ 𝑘, it’s easy to check whether 𝑚|𝑛. 6
Examples of NP problems TSP (travelling salesperson):On a weighted graph,find a closed cycle visiting each vertex exactly once,with the total weight on the path no more than k. Easy to check:Given a cycle,easy to calculate the total weight
Examples of NP problems ◼ TSP (travelling salesperson): On a weighted graph, find a closed cycle visiting each vertex exactly once, with the total weight on the path no more than 𝑘. ◼ Easy to check: Given a cycle, easy to calculate the total weight. 7
Graph Isomorphism:Given two graphs Gi and G2,decide whether we can permute vertices of G1 to get G2. 2 1→2,2→1 3→3,4→4 30 4 G2 Easy to check:For any given permutation,easy to permute G1 according to it and then compare to G2. 8
◼ Graph Isomorphism: Given two graphs 𝐺1 and 𝐺2 , decide whether we can permute vertices of 𝐺1 to get 𝐺2 . ◼ Easy to check: For any given permutation, easy to permute 𝐺1 according to it and then compare to 𝐺2 . 1 2 3 4 3 4 1 2 1 → 2, 2 → 1 3 → 3, 4 → 4 𝐺1 𝐺2 8
Question of P vs.NP ■ISP=NP? The most famous (and notoriously hard) question in computer science. 0 Staggering philosophical and practical implications Withstood a great deal of attacks Clay Mathematics Institute recognized it as one of seven great mathematical challenges of the millennium.US$1M. ▣Vant to get rich(and famous)？Here is a“simple”wayl 9
Question of P vs. NP ◼ Is P = NP? ◼ The most famous (and notoriously hard) question in computer science. ❑ Staggering philosophical and practical implications ❑ Withstood a great deal of attacks ◼ Clay Mathematics Institute recognized it as one of seven great mathematical challenges of the millennium. US$1M. ❑ Want to get rich (and famous)? Here is a “simple” way! 9
The P vs.NP question:intuition Is producing a solution essentially harder than checking a solution? Coming up with a proof vs.verifying a proof. Composing a song vs.appreciating a song. Cooking good food vs.recognizing good food 10
The P vs. NP question: intuition ◼ Is producing a solution essentially harder than checking a solution? ❑ Coming up with a proof vs. verifying a proof. ❑ Composing a song vs. appreciating a song. ❑ Cooking good food vs. recognizing good food ❑ … 10