4.2问题的计算复杂性分类 4.21P,NP,NP完全类问题 定义48一个语言L的成员识别问题属于P类,若存在 个可解该问题的图灵机M和一个正多项式p(m),使 M的计算复杂性f(n)=O(D(m),所有P类问题构成 的集记作P。 定义49一个语言的成员识别问题属于NP类,若存 在 o0×⑨的子集R={xy)}(称为一个布尔关系) 及一个正多项式p(n)满足下列两个条件: 1)R2的成员识别问题属于P类 2)x∈L当且仅当存在一个y,其长川以(x),且(xy)∈B 这样的y称为是x∈L的证据。所有NP类问题构成的集 记作N4．2 问题的计算复杂性分类 • 4.2.1 P，NP，NP完全类问题 • 定义4.8 一个语言L的成员识别问题属于P类，若存在 一个可解该问题的图灵机M和一个正多项式 ，使 M的计算复杂性 ，所有P类问题构成 的集记作P。 • 定义4.9 一个语言L的成员识别问题属于NP类，若存 在一个 的子集 （称为一个布尔关系） 及一个正多项式p(n)满足下列两个条件： 1） 的成员识别问题属于P类； 2） 当且仅当存在一个y，其长 ，且 。 这样的y称为是 的证据。所有NP类问题构成的集 记作NP。 p(n) f (n) (p(n)) M =      * * 0,1  0,1 RL = (x, y) RL x L y  p( x ) RL (x, y) x L