Computational Complexity ·decision problem f:{0,1}*→{0,1} 。formal language L{0,1}*L={x∈{0，l}*|fx)=1〉 poly-time Turing machine (algorithm)M: 3c>0 .Vx∈{0，l}*,M()terminates within)steps length of x (in bits) P,NP:classes of formal languages (decision problems) ·L∈P:3poly--time TM M decides L ·M(x)=1fx∈L ·L∈NP:3 polynomial p(·)and poly-time TM M that verifies L ·x∈L→3 certificate y∈{0,1}*of length p(x),M(x,y)=l; ·x庄L→y∈{0，l}*of length p(xl),M(x,y)=0;• decision problem • formal language • poly-time Turing machine (algorithm) : • , terminates within steps • : classes of formal languages (decision problems) • : poly-time TM decides • iff • : polynomial and poly-time TM that verifies • certificate of length , ; • of length , ; f : {0,1}* → {0,1} L ⊆ {0,1}* L = {x ∈ {0,1}* ∣ f(x) = 1} M ∃c > 0 ∀x ∈ {0,1}* M(x) O(| x | c ) P, NP L ∈ P ∃ M L M(x) = 1 x ∈ L L ∈ NP ∃ p( ⋅ ) M L x ∈ L⟹∃ y ∈ {0,1}* p(| x |) M(x, y) = 1 x ∉ L⟹ ∀y ∈ {0,1}* p(| x |) M(x, y) = 0 Computational Complexity length of x (in bits)