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