NP完全性: P类(即多项式类): 具有多项式复杂性算法的问题集,如果存在 多项式p(s),对任何问题规模s的时间复杂性为 0(p(s),则某算法即具有多项式复杂性 NP类(即不确定性多项式类):能以多项式时 间,用不确定性算法求解的问题集。 PCNP 口确定性算法是不确定算法的特殊情况。 P类问题是计算易解的,而NPP类问题是难 解的。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ NP完全性： ◼ P类(即多项式类)： ❑ 具有多项式复杂性算法的问题集，如果存在一 多项式p(s)，对任何问题规模s的时间复杂性为 O(p(s))，则某算法即具有多项式复杂性。 ◼ NP类(即不确定性多项式类)：能以多项式时 间，用不确定性算法求解的问题集。 ◼ PNP ❑ 确定性算法是不确定算法的特殊情况。 ◼ P类问题是计算易解的，而NP-P类问题是难 解的
现在不知道是否P=NP或P≠NP。 难解的NP类问题又称为具有指数时间 复杂性的问题。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ 现在不知道是否P＝NP或P≠NP。 ◼ 难解的NP类问题又称为具有指数时间 复杂性的问题
例题:多项式复杂性和指数复杂性 算法 将几个数排序的多项式时间复杂性 分别为0( nlogn),属于P类 对两个n×n矩阵相乘算法的多项式 时间复杂性分别为0(n3),属于P类。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ 例题：多项式复杂性和指数复杂性 算法： ◼ 将几个数排序的多项式时间复杂性 分别为O(nlogn)，属于P类 ◼ 对两个n×n矩阵相乘算法的多项式 时间复杂性分别为O(n3)，属于P类
旅行推销员问题复杂性为0(n22)和 背包问题的复杂性为0(2n2) 指数复杂性问题是属NP类的: 口到目前为止还未发现这类问题的确定 性多项式算法。 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 ◼ 旅行推销员问题复杂性为O(n22 n)和 背包问题的复杂性为O(2n/2 ) ◼ 指数复杂性问题是属NP类的： ❑ 到目前为止还未发现这类问题的确定 性多项式算法
P、NP和NPC(N完全问题) NP NP:不确定多项式时间类 NPC))P:多项式时间类 NPG:NP完全问题 推测NP,P和NPC类计算问题之间的关系 哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院 P、NP和NPC（ NP完全问题）