1、 图灵机中图灵机中无限长的带无限长的带被分成一个个小空格，被分成一个个小空格，每格容纳一个符号，对每一部图灵机而言，带上每格容纳一个符号，对每一部图灵机而言，带上允许使用的符号是有限的；允许使用的符号是有限的； 图灵机的输入图灵机的输入是由符号组成的有限序列，称是由符号组成的有限序列，称之为符号行，输入符号行不能含空格符之为符号行，输入符号行不能含空格符B。 读写头读写头每次左或右移动一格，并根据控制器每次左或右移动一格，并根据控制器的指令阅读方格中的符号或抹去、重写方格中的的指令阅读方格中的符号或抹去、重写方格中的符号，其初始位置是输入符号行最左边符号。符号，其初始位置是输入符号行最左边符号
2、。读写头读写头 带带（B B表示空格）表示空格） B 0 1 1 0 0 0 B控制器控制器 控制器控制器有有限个状态，其中启始状态和有有限个状态，其中启始状态和终止状态是两个特殊的状态；状态可依终止状态是两个特殊的状态；状态可依转移转移函数函数进行，进行，（q，a）=（p，b，v）意为：）意为：读写头看到符号读写头看到符号a时，处于状态时，处于状态q的控制器命的控制器命令其抹掉令其抹掉a，重写，重写b，并向，并向v（左或右）移动（左或右）移动一格，状态改变为一格，状态改变为p； 控制器开始处于启始状态，图灵机当且控制器开始处于启始状态，图灵机当且仅当控制器处于终止状态时停止，此时仅当控制器处
3、于终止状态时停止，此时带上带上符号行符号行为输出。为输出。 显然，图灵计算机计算的是显然，图灵计算机计算的是从符号行到符号从符号行到符号行的函数行的函数，但并不太限制其应用范围，但并不太限制其应用范围,它的它的计算计算时间时间是指读写头的移动次数是指读写头的移动次数,计算占用的空间计算占用的空间是是指带上被访问过的方格数指带上被访问过的方格数,当输入符号行是当输入符号行是x时时,图图灵机灵机M的计算时间的计算时间(或占用空间或占用空间)记为记为Time M(x) (或或Space M(x)。 图灵精彩地论证了图灵精彩地论证了 一个典型问题就是一个典型问题就是：给定给定一个带有输入的计算机程序，
4、它会停机吗？一个带有输入的计算机程序，它会停机吗？图灵证明了，不存在一个算法能对该问题的图灵证明了，不存在一个算法能对该问题的一切例子给出正确的答案。一切例子给出正确的答案。 对于给定的问题，如果对于给定的问题，如果存在一种算法，可存在一种算法，可以对该问题的一切例子给出正确的答案，那以对该问题的一切例子给出正确的答案，那麽这个问题就是麽这个问题就是的。的。 可重复性可重复性归根于归根于，这，这种确定性也是当今世界上存在的各式各样计种确定性也是当今世界上存在的各式各样计算机的共同特点。算机的共同特点。若若f(x)f(x)无定义无定义, ,则对输入则对输入x, Mx, M的任何计算的任何计算道路
5、都是道路都是( (时间时间) )无限长的无限长的; ;若若f(x)f(x)有定义有定义, ,则对输入则对输入x, Mx, M必有一有限长必有一有限长的道路；并且对任何有限长的计算道路，计的道路；并且对任何有限长的计算道路，计算结果都是算结果都是f(x)f(x)。 对这种图灵机对这种图灵机 M M，Time Time M M（x x）表示输入）表示输入x x时，时，M M可能使用的最短时间可能使用的最短时间，Space Space M M（x x）表示输入表示输入x x时，时，M M可能使用的最少空间可能使用的最少空间。可以可以在不确定型计算机上实施的计算称为在不确定型计算机上实施的计算称为。（
6、Non-deterministic computationNon-deterministic computation） 。与此有关的因素有：与此有关的因素有：一般指问题的输入长度一般指问题的输入长度为了衡量算法的效果所广泛采用的为了衡量算法的效果所广泛采用的是：是： 为了避免由于不同输入而对算法行为了避免由于不同输入而对算法行为产生巨大差别，考察所有规模为为产生巨大差别，考察所有规模为n n的的输入输入，。因此，算法复杂性是输入因此，算法复杂性是输入规模的函数，比如规模的函数，比如10n10n3 3,2,2n n,nlog,nlog2 2n n等。等。输入规模足够大时，在复杂性函数中，输入规模
7、足够大时，在复杂性函数中，较慢的项（如较慢的项（如nlognlog2 2n+5nn+5n），终将被增长），终将被增长速度很快的项超过（该例中速度很快的项超过（该例中n1000n1000时，时，nlognlog2 2n5nn5n）。）。只有规模大的输入，才能确定只有规模大的输入，才能确定。比如复杂性为。比如复杂性为10n10n3 3与复杂性为与复杂性为9n9n3 3的算的算法间的差别可以忽略不计，因为这可以通过技法间的差别可以忽略不计，因为这可以通过技术革新，使计算机速度提高术革新，使计算机速度提高1010倍而得到补偿。倍而得到补偿。(c)(c)如果存在两个常数如果存在两个常数c,c0,c,c0
8、,使得当使得当n n足够大时有足够大时有cg(n)f(n)cg(n),cg(n)f(n)cg(n),则记则记f(n)=g(n)f(n)=g(n)，用记号，用记号f(n)g(n)f(n)g(n)代替代替f(n)=(g(n),f(n)=(g(n),易见易见是一个等是一个等价关系，在该等价关系下，价关系，在该等价关系下，f(n)f(n)的等价类（即的等价类（即f(n)=(g(n)f(n)=(g(n)的所有的所有g(n)g(n)的集合）称为的集合）称为 设设f(n),g(n)f(n),g(n)是定义在正整数上的正实值函数是定义在正整数上的正实值函数(a)(a)如果存在一个常数如果存在一个常数c0,c0
9、,使得当使得当n n足够大时足够大时, ,有有f(n)cg(n),f(n)cg(n),则记则记f(n)=O(g(n)f(n)=O(g(n)；(b)(b)如果存在一个常数如果存在一个常数c0,c0,使得当使得当n n足够大时有足够大时有f(n)cg(n),f(n)cg(n),则记则记f(n)=(g(n)f(n)=(g(n)； 算法分析中常常使用算法分析中常常使用初等运算初等运算算术算术运算、比较、转移指令等运算、比较、转移指令等的步数的步数表示一个算表示一个算法在假设的计算机上执行时所需的时间，即法在假设的计算机上执行时所需的时间，即每做一次初等运算，需要一个单位时间。而每做一次初等运算，需要一
10、个单位时间。而当把算法当把算法的输入表示为符号串时，那麽的输入表示为符号串时，那麽输入规模输入规模就定义为该符号串的长度就定义为该符号串的长度（符号串中符（符号串中符号的数目），称为号的数目），称为。例例1以某一个固定数为基底的运算系统（如十进以某一个固定数为基底的运算系统（如十进制 或 二 进 制 ） 中 ， 表 示 一 个 整 数制 或 二 进 制 ） 中 ， 表 示 一 个 整 数 n 的 输 入 规的 输 入 规模：模： ，因为，因为logBn=logn/logB, B固定后固定后logB是是一个常数。一个常数。nBlog例例2.试分析试分析LP的规模的规模. 设设A、b、c中的元素均
11、为整数，则中的元素均为整数，则LP的规模就的规模就是表示是表示A、b、c所需符号的数目。因为可以把二进所需符号的数目。因为可以把二进制（十进制）表示的矩阵中元素排成一行，用符号制（十进制）表示的矩阵中元素排成一行，用符号线适当地隔开以表示矩阵的行或列，从而矩阵也可线适当地隔开以表示矩阵的行或列，从而矩阵也可以表示为符号串。所以，以表示为符号串。所以，mn的的LP问题规模为问题规模为(mn+ ）其中）其中p是所有非零参数的乘积。是所有非零参数的乘积。plog决定一个算法的决定一个算法的实际效用实际效用，要看其，要看其。目。目前计算机科学家们有一个公认的看法：前计算机科学家们有一个公认的看法： 设
12、有解某种问题设有解某种问题的一个算法，对于输入长度为的一个算法，对于输入长度为L L的具体问的具体问题，其题，其计算步骤有一个上界计算步骤有一个上界P P（L L），）， 若若P P（y y）是）是y y的多项式，的多项式，则称此算法是一则称此算法是一个个（Polynomial-Time Polynomial-Time Algorithm for Linear ProgrammingAlgorithm for Linear Programming），），简称简称。 函函 数数 近近 似似 值值NNlognn3106n8 10 33 1000 1014 100 664 1000，000 1022
13、 1000 9966 109 10302nnlognn！ 1024 20993，628，800 1271030 1931013 10158 1.0510301 7.891029 4102567 当输入规模增大时，任意一个多项式算当输入规模增大时，任意一个多项式算法终将变得比指数算法更有效，见表法终将变得比指数算法更有效，见表1 1。在某种意义上，它很好地利用了技术发展的优点。在某种意义上，它很好地利用了技术发展的优点。 每次技术突破，计算机速度提高每次技术突破，计算机速度提高10倍，则多倍，则多项式算法原来项式算法原来1小时内所能解算例子的最大规模小时内所能解算例子的最大规模可增加可增加C倍，
14、其中倍，其中0C10,而指数算法所能解算而指数算法所能解算的例子规模只能增加一个常数的例子规模只能增加一个常数. 表表2显示了多项式算法利用技术发展的优点情显示了多项式算法利用技术发展的优点情况况.表表2 2 多项式算法利用技术发展的优点情况表多项式算法利用技术发展的优点情况表 函函 数数 一天内能解一天内能解例子的规模例子的规模计算机速度提高计算机速度提高10倍倍后所能解例子的规模后所能解例子的规模 n nlogn n2 n3 108n4 1012 0.9481011 106 104 10 1013 0.871012 3.16106 2.15104 18 2n 10n nlogn n! 40
15、 12 79 14 43 13 95 15 n n个多项式算法可以结合起来解同个多项式算法可以结合起来解同一问题的某些特殊情形；一问题的某些特殊情形； 一个多项式算法也可以利用另一一个多项式算法也可以利用另一个多项式算法作为个多项式算法作为“子程序子程序”，并且，并且最后的结果仍然是一个多项式算法。最后的结果仍然是一个多项式算法。 称具有多项式时间算法的一类问题为称具有多项式时间算法的一类问题为P P类类问题问题，简称，简称P P问题问题。如：有向图中的路、最大。如：有向图中的路、最大匹配问题、最小支撑树问题等；匹配问题、最小支撑树问题等； NPNP类问题类问题也叫不确定性问题（或称非多项式也
16、叫不确定性问题（或称非多项式确定问题）。如果有一个用于求解此问题的算确定问题）。如果有一个用于求解此问题的算法，对于它可以找到一个多项式时间算法来验法，对于它可以找到一个多项式时间算法来验证该算法所得的结果是否为此问题的解，则称证该算法所得的结果是否为此问题的解，则称此问题属于此问题属于NPNP类问题，简称类问题，简称NPNP问题问题。NPNP完备的（完备的（NP-CompleteNP-Complete）如果一个判如果一个判定问题定问题A A是是NPNP的，而且所有其他的，而且所有其他NPNP问题都能多问题都能多项式地归结到项式地归结到A A，则称，则称A A是是NPNP完备的。完备的。 所谓
17、所谓多项式地归结，多项式地归结，指的是指的是多项式地时间归多项式地时间归结，结，其定义是：其定义是：设设A A1 1、A A2 2都是判定（即是都是判定（即是- -否）问题，说否）问题，说A A1 1在多项式在多项式时间内归结为时间内归结为A A2 2，当且仅当，当且仅当A A1 1有个多项式时间算法有个多项式时间算法 ，并且，并且是多次地以单位费用把是多次地以单位费用把A A2 2的算法的算法A2用用作子程序的算法。则把作子程序的算法。则把叫做叫做A A1 1到到A A2 2的多项式时间的多项式时间归结。归结。：如果：如果A1多项式归结到多项式归结到A2，而，而A2有多项式算法，有多项式算法
18、，则则A1也有多项式算法也有多项式算法 。 常用的证明一个问题为常用的证明一个问题为P P的方法一、的方法一、先先设计出求解问题设计出求解问题的一个算法的一个算法；然后证明其；然后证明其正确正确性性，即可利用该算法精确求解问题，即可利用该算法精确求解问题；最后，通过；最后，通过仔细分析算法的实现过程来估计它所需的总的计算仔细分析算法的实现过程来估计它所需的总的计算工作量，即其工作量，即其计算复杂性计算复杂性，若所得估计值可用问题，若所得估计值可用问题规模参数（如输入长度、问题维数等）的一个多项规模参数（如输入长度、问题维数等）的一个多项式函数来界定，则表明该算法为多项式时间算法，式函数来界定，
19、则表明该算法为多项式时间算法，从而得到问题从而得到问题P P属于属于。如背包问题、排序问题等。如背包问题、排序问题等 常用的证明一个问题为常用的证明一个问题为P P的方法二、的方法二、通过某种转换或逻辑推理来进行。通过某种转换或逻辑推理来进行。常见的技巧有：常见的技巧有：证明可采用一些简单的、可在多项式时间内完成的证明可采用一些简单的、可在多项式时间内完成的变换方法，将原问题转换为另一已知的变换方法，将原问题转换为另一已知的P P类问题的类问题的求解；说明可通过递推、分解等方法来对原问题进求解；说明可通过递推、分解等方法来对原问题进行简化，使简化后的问题很容易在多项式时间内求行简化，使简化后的
20、问题很容易在多项式时间内求解，而所采用的分解等策略也可在多项式时间内完解，而所采用的分解等策略也可在多项式时间内完成；直接考察原问题的可行解所可能存在的各种情成；直接考察原问题的可行解所可能存在的各种情形，当然这些可能的不同情形不会超过问题规模的形，当然这些可能的不同情形不会超过问题规模的某个多项式，并说明在每种情况下均可在多项式时某个多项式，并说明在每种情况下均可在多项式时间内求解原问题间内求解原问题 COOKCOOK定理定理 为了证明一个问题是为了证明一个问题是NP-NP-完备的，我们必须证完备的，我们必须证明两件事：明两件事：(a)(a)该问题是该问题是NPNP的的(b)(b)所有其他所
21、有其他NPNP问题多项式转换到该问题问题多项式转换到该问题in stan ce$certificate符号串程序读写头 通过通过COOKCOOK定理可以证明得出以下定理定理可以证明得出以下定理定理定理1:1:适定性是适定性是NPNP完备的完备的定理定理2:2:适定性是适定性是NPNP完备的完备的定理定理3:3:团是团是NPNP完备的完备的定理定理4:4:对于图对于图G=(V,E)G=(V,E)和和V V的子集的子集S S，下述三个判断，下述三个判断 是等价的：是等价的：a)a) S S是是G G的一个团的一个团b)b) S S是是G G的补图的补图G G的独立集的独立集c)c) V-SV-S是
22、是G G的点覆盖的点覆盖 - - - 通过通过COOKCOOK定理可以证明得出以下定理定理可以证明得出以下定理定理定理5:5:多处理时间表是多处理时间表是NP-NP-完备的完备的定理定理6:6:哈密顿圈是哈密顿圈是NP-NP-完备的完备的推论一推论一: :哈密顿路问题是哈密顿路问题是NP-NP-完备的完备的推论二推论二: : 货郎问题是货郎问题是NP-NP-完备的完备的定理定理7:7:维匹配问题是维匹配问题是NPNP完备的完备的定理定理8:0-18:0-1背包问题是背包问题是NPNP完备的完备的推论一推论一: :划分是划分是NP-NP-完备的完备的推论二推论二: : 整数背包是整数背包是NP-NP-完备的完备的 NP-hardNP-hard（NPNP难）问题难）问题 若若NPNP中任何一个问题可在多项式时间归结中任何一个问题可在多项式时间归结为判定问题为判定问题A A，则称，则称A A为为NPNP难或难或NP-hardNP-hard问题。问题。图图2 2 算法复杂性的四类问题关系图算法复杂性的四类问题关系图 P NP NPC NP-hard
