CSC3160: Design and Analysis of Algorithms Week 10: NP-completeness Instructor: Shengyu Zhang 1
Instructor: Shengyu Zhang 1
Tractable While we have introduced many problems with polynomial-time algorithms... ..not all problems enjoy fast computation. Among those“hard”problems,an important class is NP. 2
Tractable ◼ While we have introduced many problems with polynomial-time algorithms… ◼ …not all problems enjoy fast computation. ◼ Among those “hard” problems, an important class is NP. 2
P,NP P:Decision problems solvable in deterministic polynomial time NP:two definitions Decision problems solvable in nondeterministic polynomial time. Decision problems (whose valid instances are) checkable in deterministic polynomial time Let's use the second definition. Recall:A language L is just a subset of {0,1*, the set of all strings of bits. ▣{0,1*=Un2o{0,1”. 3
P, NP ◼ P: Decision problems solvable in deterministic polynomial time ◼ NP: two definitions ❑ Decision problems solvable in nondeterministic polynomial time. ❑ Decision problems (whose valid instances are) checkable in deterministic polynomial time ◼ Let’s use the second definition. ◼ Recall: A language 𝐿 is just a subset of 0,1 ∗ , the set of all strings of bits. ❑ 0,1 ∗ = ڂ≤��0 0,1 𝑛 . 3
Formal definition of NP Def.A language L∈{0，l}*is in NP if there exists a polynomial p:N->N and a polynomial- time Turing machine M such that for every x E {0,1}*, xeL台]u∈{0,1plxs.t.M(x,u)outputs1 M:the verifier for L. For xe L,the u on the RHS is called a certificate for x(with respect to the language L and machine M). So NP contains those problems easy to check
Formal definition of NP ◼ Def. A language 𝐿 ⊆ 0,1 ∗ is in NP if there exists a polynomial 𝑝: ℕ → ℕ and a polynomialtime Turing machine 𝑀 such that for every 𝑥 ∈ 0,1 ∗ , 𝑥 ∈ 𝐿 ⇔ ∃𝑢 ∈ 0,1 𝑝 𝑥 𝑠.𝑡. 𝑀(𝑥, 𝑢) outputs 1 ◼ 𝑀: the verifier for 𝐿. ◼ For 𝑥 ∈ 𝐿, the 𝑢 on the RHS is called a certificate for 𝑥 (with respect to the language 𝐿 and machine 𝑀). ◼ So NP contains those problems easy to check. 4
SAT and k-SAT SAT formula:AND of m clauses n variables (taking values 0 and 1) a literal:a variable x;or its negationi m clauses,each being OR of some literals. SAT Problem:Is there an assignment of variables s.t.the formula evaluates to 1? k-SAT:same as SAT but each clause has at most k literals. SAT and k-SAT are in NP. Given any assignment,it's easy to check whether it satisfies all clauses. 5
SAT and 𝑘-SAT ◼ SAT formula: AND of 𝑚 clauses ❑ 𝑛 variables (taking values 0 and 1) ❑ a literal: a variable 𝑥𝑖 or its negation 𝑥ഥ𝑖 ❑ 𝑚 clauses, each being OR of some literals. ◼ SAT Problem: Is there an assignment of variables s.t. the formula evaluates to 1? ◼ 𝑘-SAT: same as SAT but each clause has at most 𝑘 literals. ◼ SAT and 𝑘-SAT are in NP. ◼ Given any assignment, it’s easy to check whether it satisfies all clauses. 5
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