1、专题一 计算机科学基础【主要内容】1基础知识2可计算性3计算复杂性4求解 NP 问题的基本思路5进一步理解 NP 问题一、简介 本讲主要介绍可计算性与计算复杂性理论涉及到的最基本知识以及相关概念，集中在计算理论的可计算性与计算复杂性。计算机的基本能力和限制是什么？这个问题要回溯到 20 世纪 30 年代，那时数理逻辑学家们首先开始探究计算的含义。自那时起以来，技术进步极大地增强了我们的计算能力，并且把这个问题从理论王国带进现实世界。在可计算性与计算复杂性中的每一个领域内，对这个问题作了不同的解释，并且答案随着解释的不同而各不相同。我们将分别介绍可计算性和计算复杂性的相关知识。1. 可计算性理论
2、对于计算机这门学科，他的最基本问题是要考虑研究对象是什么的问题，换言之，什么是可以计算的，什么是不可以计算的。这就引出了计算机科学领域的一个非常重要的概念：可计算性。 在 21 世纪前半叶，数学家们，如歌德尔(Kurt Gdel)、图灵(Alan Turing)及丘奇(Alonzo Church)，发现一些基本问题是不能用计算机解决的。确定一个数学命题是真是假就是一个例子。这项工作是数学家的生计。用计算机来解决似乎是天经地义的，因为这是数学王国里的事。但是，没有计算机算法能够完成这项工作。关于计算机理论模型思想的发展是这一意义深远的结论的成果之一，它最终促使建造出实际的计算机。可计算理论与复杂
3、性理论是密切相关的。在复杂性理论中，目标是把问题分成容易的和困难的；而在可计算理论中，是把问题分成可解的和不可解的。2. 计算复杂性理论计算的问题是各种各样的，有的容易，有的困难。例如，排序是一个容易的问题，比如说需要按升序排列一张数表，即使一台小型计算机都相当快地处理 100 万个数。与时间表问题比较一下，比如说要制定一所大学的课程表，课程表必须满足某些合理的限制，如不能有两个班在同一时间使用同一教室。时间表问题看来比排序问题困难得多。如果有 1000 个班，即使是使用一台超级计算机，制定一份最好的课程表也可能需要若干世纪。是什么使某些问题很难计算，又使另一些问题容易计算？这是复杂性理论的核
4、心问题。值得注意的是，虽然在过去的二十多年里对它进行了深入细致的研究，但是我们仍然不知道它的答案。以后我们将探究这个迷人的问题和它的一些分支。迄今为止，复杂性理论的一个重要成果是，发现了一个按照计算难度给问题分类的完美体系。它类似按照化学性质给元素分类的周期表。运用这个体系，我们能够提出一种方法给出某些问题是难计算的证据，尽管还不能证明它们是难计算的。当你面对一个看来很难计算的问题时，有几种选择。首先，搞清楚问题困难的原因，你可能会做某些变动，使问题变的容易解决。其次，你可能会求出问题的不那么完美的的解。在某些情况下，寻找问题的近似解相对容易一些。第三，有些问题仅仅在最坏的情况下是困难的，而在
5、绝大多数的时候是容易的。就应用而言，一个偶尔运行得很慢、而通常运行得很快的过程是能够令人满意的。最后，你可以考虑其他类型的计算，如随机计算，它能够加速某些工作。受到复杂性理论直接影响的一个应用领域是密码技术，这是一个古老的研究领域。在绝大多数的情况下，容易计算的问题比难计算的问题更可取，因为求解容易的问题的代价要小。密码技术与众不同，它特别需要难计算的问题，而不是容易计算的问题。在不知道密钥或口令时，密码应该是很难破译的。复杂性理论给密码研究人员指出了寻找计算问题的方向，围绕这些问题已经设计出新的革命性的编码。二、可计算性与图灵机 1. 可计算函数 在这一节将引进整个讲义的最基本概念可计算函数
6、。设 P 为一 n 元程序，则对每组输入值x1a1,x2=a2, xn=an都计算出一个值 y，因此可使每一个程序 P 对应一个函数。不同的程序可对应于同一函数。设 P 是以 x1,x2,xn 为输入变量的 n 元程序，则将用jp(x1, x2, ,xn)表示程序 P 所对应的函数。具体如下：因此 jp2(x1，x2)是无定义函数。上面两个程序是处处无定义的一元和二元函数。定义 1 函数 f (x1，x2，xn)被称为部分可计算的，若有一程序 P 使得jp (x1，x2，xn)= f (x1 ，x2 ，xn)这里等号“=”表示：或者两边都无定义，或者两边都有定义并且其值相同。定义 2 函数 f
7、 (x1，x2，xn)被称为全函数，若它对一切 x1，x2，xn 的值都有定义。定义 3 函数 f (x1，x2，xn)被称为可计算函数，若它是部分可计算的而且是全函数。可计算函数不只要求有计算它的程序，且要求永远有定义。可计算函数是部分可计算函数的特殊情形图 2.12. 图灵机 现在开始研究一种新的计算装置Turing(图灵机)。Turing 机和 Post-Turing 机类似，它有一个带和指针Turing 和 Post-Turing 机一样有三个基本动作：1. 往带上输出符号2. 把指针右移一格；3. 把指针左移一格。每个 Turing 机都有自己的字母表和状态集：字母表 S=S0，S1
8、，S2，SK状态集 Q=q1，q2，q3，qN在状态集中有一个特殊的状态叫做初始状态。我们假定 q1 为初始状态。Turing 机的每步动作由所谓的四元组来确定。每个四元组完成一个基本动作并转入下一个状态。四元组有三类，具体如下：四元组中 L 和 R 是特殊符，它们区别于字母表中符号 Si。四元组中前两个符号表示条件，第三个符号表示动作内容，第四个符号表示要转入的下一个状态。图灵用形式化方法成上述这种功地表述了计算这一过程的本质：所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串 0 和 1执行指令，一步一步地改变纸带上的 0 或 1，经过有限步骤，最后得到一个满足预先规定的符号
9、串的变换过程。 图灵机具有如下性质： 定义 3 函数 f(x1，x2，xn) 是 Turing 部分可计算的。若有Turing 机计算它。(而不是程序)定义 4 函数 f(x1，x2，xn) 是 Turing 可计算的，若函数 f(x1，x2，xn)是 Turing 部分可计算并且是全函数。由图灵机存在一个重要的论题： Church-Turing 论题：凡是可计算的过程都可用图灵机实现； 换言之，图灵机的计算能力要强于目前任何一台计算机，计算机科学所处理的研究对象是：可以被图灵机实现的计算问题 三、计算复杂性与图灵机 1. P 问题与 NP 问题 考虑计算复杂类中最常见的两类问题：P 类和 N
10、p 类问题，我们可以利用图灵机对 P 和 NP 问题进行划分： P 类 确定性图灵机在多项式时间内可以判定的问题 NP 问题： 在非确定型图灵机上多项式时间可解的问题 由上可知，P 类包含于 NP 类中。 P 与 NP 的另一种定义： 多项式时间算法，设某算法 C 的时间复杂度是 ，其中 是问题规模，有 ， 是多项式函数，则称 C 算法是多项式时间算法。即：时间复杂度函数是 的算法 指数时间算法：时间复杂性函数不能表示成 的算法（包括： ：非多项式函数，不是指数函数） P 类问题有多项式时间算法解决的判定问题。 NP 类问题对问题的一个猜想存在多项式时间算法来验证它的判定问题2. NP 完全问
11、题和 NP 难问题 NP 完全问题：我们称一个问题 q 是 NP 完全的，那么 q 满足如下性质： o q 是 NP 的 o 对于任意的一个 NP 问题 q0，都可以在多项式的时间转换为等价的 q 问题 换言之，要证明一个问题是 NP 完全的，首先需要证明它至少是一个 NP 问题，再证明其中一个已知的 NP 完全问题能约化到它。根据 NP 完全问题的定义可以看出，如果我们可以证明一个 NP 完全问题可以在多项式时间求解，那么 P 等于 NP。因为既然所有的 NP 问题都能约化成 NP 完全问题，那么只要任意一个 NP 完全问题找到了一个多项式的算法，那么所有的 NP 问题都能用这个算法解决了，NP 也就等于 P 了。 NP 难问题和 NP 完全问题的区别在于，不需要满足上述性质中的第一个性质，从这我们可以看出 NP 难问题要比 NP 完全问题更为困难。 3. NP 完全问题实例 问题 1 图着色问题 判定问题：是否存在不超过 k 种颜色的着色方案?
