P vs.NP P:problems that can be easily solved a“easily”:in polynomial time NP:problems that can be easily verified. Formally:3 a polynomial time verifier V,s.t.for any input x, If the answer is YES,then 3y s.t.V(x,y)=1 If the answer is NO,then Vy,V(x,y)=1 The question of TCS:Is P NP? Intuitively,no.NP should be much larger. It's much easier to verify(with help)than to solve(by yourself) mathematical proof,appreciation of good music/food,... Formal proof?We don't know yet. One of the 7 Millennium Problems by CMI. 1http://www.claymath.org/millennium/P_vs_NP/P vs. NP ◼ P: problems that can be easily solved ❑ “easily”: in polynomial time ◼ NP: problems that can be easily verified. ❑ Formally: ∃ a polynomial time verifier V, s.t. for any input x, ◼ If the answer is YES, then ∃y s.t. V(x,y) = 1 ◼ If the answer is NO, then ∀y, V(x,y) = 1 ◼ The question of TCS: Is P = NP? ❑ Intuitively, no. NP should be much larger. ◼ It’s much easier to verify (with help) than to solve (by yourself) ◼ mathematical proof, appreciation of good music/food, … ❑ Formal proof? We don’t know yet. ◼ One of the 7 Millennium Problems by CMI.① ① http://www.claymath.org/millennium/P_vs_NP/