1、 第 8课 计算复杂性第 3章 计算复杂性与智能算法第 8课 计算复杂性第 9课 近似算法第 10课 智能型算法第 11课 线性规划第 8课 计算复杂性第 8课 计算复杂性 算法复杂性问题 图灵机 P类与 NP类问题 NP完全问题第 8课 计算复杂性 算法的复杂性问题 算法本身能不能解，这个问题应该在求解问题前就应该首先确定，因为如果一个问题是不可解的，那么对这个问题寻求算法的努力也是徒劳的。问题否可解的相关内容，也就是算法复杂性理论所涉及到的内容。包括 P、NP问题的定义以及比较，还有确定型图灵机的介绍。这些内容不足以构成算法复杂性理论体系，但是了解这些内容是复杂性理论深入学习的基础。 计算
2、复杂性问题第 8课 计算复杂性可解问题与不可解问题并不是任何计算问题都能够利用计算机来解决。算法复杂性理论关心的是哪些问题是可以利用计算机来解决的，也就是说是 “ 可解的问题 ” ；哪些问题是在计算机也解决不了的，也就是 “ 不可解的问题 ” 。尽管理论上可解的问题在实际中未必能够找到实现的算法，但算法复杂性理论关心的是如何在理论上证明问题的可解，而不关心具体如何实现。 计算复杂性问题第 8课 计算复杂性 P问题与 NP问题 如果一个判定性问题的复杂度是该问题的一个实例的规模 n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于 P类问题。 P类问题就是所有复杂度为多项式时间的问
3、题的集合。通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题。这种可以在多项式时间内验证一个解是否正确的问题称为 NP问题 ,亦称为易验证问题类。 计算复杂性问题第 8课 计算复杂性 NP理论的核心问题如果说 P问题是 NP问题的一个真子集，那么可以不必花太多时间寻找大规模输入 NP问题的解，因为这样的努力都是徒劳的；然而如果能够证明 NP问题是 P问题，那么结果就很不一样了，它说明了现在许多的指数复杂度的问题都有多项式复杂度的解法，只不过是暂时找不到而已。 计算复杂性问题第 8课 计算复杂性 三种常用计算模型.随机存取机 RAM模型.随机存取存储程序机 RASP模型.图灵机
4、模型 计算复杂性 问题第 8课 计算复杂性 随机存取机 RAM1. RAM的结构计算复杂性 问题第 8课 计算复杂性2. RAM程序一个 RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作 2种不同的解释。解释一： 把 RAM程序看成是计算一个函数若一个 RAM程序 P总是从输入带前 n个方格中读入 n个整数 x1， x2， ， xn， 并且在输出带的第一个方格上输出一个整数 y后停机，那么就说程序 P计算了函数f(x1， x2， ， xn)=y 计算复杂性 问题第 8课 计算复杂性解释二： 把 RAM程序当作一个语言接受器将字符串 S=a1a2 an放在输入带上。在输入带的第一个方格中放入符号 a1， 第二个方格中放入符号 a2， ， 第 n个方格中放入符号 an。 然后在第 n+1个方格中放入 0，作为输入串的结束标志符。如果一个 RAM程序 P读了字符串 S及结束标志符 0后，在输出带的第一格输出一个 1并停机，就说程序 P接受字符串 S。 计算复杂性 问题
