什么是 NP-hard，思考中 转载自 摘自某 BBS：存在许多还没找到有效算法的问题也许其中最著名的要数图论中的“旅行推销员问题”，简称“TSP”即“已给一个 n 个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”Edmonds，Cook 和 Karp 等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法这些问题称为 NP 难题（NP-Hard 或 NPH）迄今为止，这类问题中没有一个找到有效算法目前倾向于接受 NP 完全问题（NP-Complet 或NPC）和 NP 难题不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法计算复杂性理论源于对判定问题算法的研究判定问题：其答案不是“是”就是“否”的问题如，一个图的两顶点之间存在路径吗？判定问题有三类：P、NP 和 NPCP 类：已有多项式时间算法的判定问题NP 类：已有指数时间算法的判定问题，包括 P 类NPC 类：是 NP 的一个子集，且其中每一个问题均能由 NP 中的任何问题在多项式时间内转化而成问题 A 能在多项式时间内转化为问题 B 可理解为，问题 A有一个算法以问题 B 的算法为子程序，当把每次对 B 算法的调用看作一个基本操作（只花常数时间）时，A 的这个算法是多项式时间的。
在 NPC 问题之外还有一些问题，其难度与 NPC 相当或难度超出 NPC，这就是NPH 问题何谓 NPH 问题呢？NPH 类：若问题 A 不属于 NP 类，已知某一 NPC 问题可在多项式时间之内转化为问题 A，则称 A 为 NP 难题例如， “TSP”是 NPH 问题摘自太傻 BBS：《第一个 NP-complete 问题》NP 是 Non-deterministic Polynomial 的缩写，NP 问题通俗来说是其解的正确性能够被很容易检查的问题，这里“很容易检查“指的是存在一个多项式检查算法例如，著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，…，等 n 个城市， 最后返回香港 任意两个城市之间都有飞机直达，但票价不等现在假设公司只给报销 $C 块钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 $C？推销员旅行问题显然是 NP 的因为如果你任意给出一个行程安排，可以很容易算出旅行总开销但是，要想知道一条总路费小于 $C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排! 这将是个天文数字。
NP-complete 问题是所有 NP 问题中最难的问题它的定义是，如果你可以找到一个解决某个 NP-complete 问题的多项式算法，那么所有的 NP 问题都将可以很容易地解决通常证明一个问题 A 是 NP-complete 需要两步，第一先证明 A 是 NP 的，即满足容易被检查这个性质; 第二步是构造一个从某个已知的 NP-complete 问题 B 到 A 的多项式变换，使得如果 B 能够被容易地求解，A 也能被容易地解决这样一来，我们至少需要知道一个 NP-complete 问题第一个 NP complete 问题是 SAT 问题，由 COOK 在 1971 年证明SAT 问题指的是，给定一个包含 n 个布尔变量（只能为真或假） X1，X2，…，Xn 的逻辑析取范式，是否存在它们的一个取值组合，使得该析取范式被满足? 可以用一个具体例子来说明这一问题，假设你要安排一个 1000 人的晚宴，每桌 10 人，共 100 桌主人给了你一张纸，上面写明其中哪些 人因为江湖恩怨不能坐在同一张桌子上，问是否存在一个满足所有这些约束条件的晚宴安排? 这个问题显然是 NP 的，因为如果有人建议一个安排方式，你可以很容易检查它是否满足所有约束。
COOK 证明了这个问题是 NP-complete 的，即如果你有一个好的方法能解决晚宴安排问题，那你就能解决所有的 NP 问题这听起来很困难，因为你必须面对所有的 NP 问题，而且现在你并不知道任何的 NP-complete 问题可以利用COOK 用非确定性图灵机（ Non-deterministic Turing Machine ） 巧妙地解决了这一问题正式地，NP 问题是用非确定性图灵机来定义的，即所有可以被非确定性图灵机在多项式时间内解决的问题非确定性图灵机是一个特殊的图灵机，它的定义抓住了“解容易被检查“ 这一特性非确定性图灵机有一个“具有魔力的“猜想部件，只要问题有一个解，它一定可以猜中例如，只要存在哪怕一个满足约束的晚宴安排方式，或是一个满足旅行预算的行程安排，都无法逃过它的法眼，它可以在瞬间猜中在猜出这个解以后，检查确认部分和一台普通的确定性图灵机完全相同，也即是等价于任何一个实际的计算机程序COOK 证明了，任意一个非确定性图灵机的计算过程，即先猜想再验证的过程，都可以被描述成一个 SAT 问题，这个 SAT 问题实际上总结了该非确定性图灵机在计算过程中必须满足的所有约束条件的总和（包括状态转移，数据读写的方式等等），这样，如果你有一个能解决该 SAT 问题的好的算法，你就可以解决相应的那个非确定性图灵机计算问题，因为每个 NP 问题都不过是一个非确定性图灵机计算问题，所以，如果你可以解决 SAT ，你就可以解决所有 NP 问题。
因此，SAT 是一个 NP-complete 问题有了一个 NP-complete 问题，剩下的就好办了，我们不用每次都要和非确定性图灵机打交道，而可以用前面介绍的两步走的方法证明其它的 NP-complete 问题迄今为止，人们已经发现了成千上万的 NP-complete 问题，它们都具有容易被检查的性质，包括前面介绍的推销员旅行问题当然更重要的是，它们是否也容易被求解，这就是著名的 P vs NP 的问题未来数学家的挑战计算量问题杨照昆;杨重骏一、前言二、计算量三、P 之外？ 四、古克定律与 NP-completeness五、NP-complete 问题之近似解六、 NP-hardness 与围棋七、结论一、前言有数学家说过「一个好的问题胜过十个好解答」因为解答一出，此问题已是到了终点，对不断求创新的人们而言，已不构成挑战而新的问题是源头活水，能开拓新的境界多数人都不愿沉醉在好的解答中不断的玩味，而希望找到新的问题，不断的思考，摸索大家在《数播》上已看见了不少好的问题，尤其最近康明昌教授谈到的费马定理，几何三大难题，都是极有趣的问题有的已有了解答，有的尚待解决除了上面的题目外，像四色问题（即任何一个地图只要用四种颜色就可以把国界分开），五次以上方程序的公式解，及数论上质数分布问题，都曾在职业及业余数学家的心目中占有相当的地位。
本文所要介绍的是一个最近（1970 年代开始）一种许多数学家及电子计算器学家所关心的大问题──NP 问题 NP 所代表的意思，你看完本文之后自然会明白，现在你不妨记住「NP-hard」这个伟大的字将来如果你对某人说你的问题是「NP-hard」，他也许就要对你刮目相看了，NP-hard 不但代表 hard（难），而且是 NP 的难！NP 问题的代表问题之一是售货员旅行问题 (traveling salesman problem)有一个售货员要开汽车到 n 个指定的城市去推销货物，他必须经过全部的 n 个城现在他有一个有此 n 城的地图及各城之间的公路距离，试问他应如何取最短的行程从家中出发再到家中？售货员之地图，A,B,C,… 表城名，数字表两城之间之里数如图 1 中，A,B,C,…,G 表示 7 个城市，而售货员要从 A 城出发再回到 A 城并访问 B,C,…,G，所有的城，一个可行的方法是问题是：这是否是最短的途径？也许更近呢？加起来的结果第一路径总长 235 里，而第二路径总长为 230 里，故第二路径较短，但是否存在一个更短的路径呢？目前的方法接近一个一个的排着试，还没有找到更好可以寻得最短路径的方法。
对七个城而言，共有 6!=720 个排法，尚不算难，但若有 20 个城，则排法就有 19! 种因故在排列组合里 n! 写起来轻松，但 1.21 x 1017 是一个大得不得了的数字，若每秒钟排一次，要排 3.84 x 109 年（一年约为 3.15 x 107 秒），即使使用计算器，每秒排一百万次（不容易做到）也得重做三千年才能找到答案 「生也有涯，知也无涯」，想不到区区二十个城，要三十个世纪才能找到答案由于电子计算器的发展，有许多以前认为枉费时的计算，像行列式之值，反矩阵，高次方程式的解，都可以在极短的时间内解决但也突然出现了一些新问题，连大型计算器也望之兴叹像售货员问题，因为找不到比硬排好得很多的做法，使得数学家们开始想要证明，根本找不到比硬排好得很多的做法这个证明至今尚未找到就像以前一角三等分问题一样，既然找了几千年找不到用圆规直尺三等分任一角的方法，也许我们可以证明绝对不可能用圆规直尺三等分一角现在我们要证明绝不可能写一个计算器程序大大的简化售货员旅行问题与三等分一角问题不同的是，前者是一种数学上的好奇，而当今的问题与实际用途却有密切的关连在此我们一直强调一个好得很多的方法原因是对这类的问题，你若能计算快一倍或十倍、千倍，往往起不了什么大作用，好像刚才的二十城旅行问题，即使快了千倍，仍需三年的计算时间，而再加三城立刻就把这个计算法的效果抵消了，因此我们所要的是计算量基本层次的减少，这就是我们在下一节所要讨论的。
二、计算量计算量，顾名思意，是指解决某问题所需要计算的时间，但因每个复杂问题的计算往往都要经过许多不同的运算，除加减乘除四则外，还要包含比较，取数据，存数据等等，若仔细计算起来，十分困难，一般都只绘出一两个主要的量，加以统计，以上节中售货员旅行问题为例，其主要的工作是对每一个排法加起总路径之长，因对 n 城而言，有 (n-1)! 的排法，我们就定其计算量为 O(n!)，即在 n! 之层次（order 即 O 缩写之来源）之内举二个例子，我们若要求 n 个数的和或平均值，则其计算量为 O(n)但若我们要把 n 个数字依次排列，则其计算量会因做法的不同而有相当的差别，一个直接了当的方法是，先求出最大的（比 (n-1) 次），再从不是最大的中间求次大的（比 (n-2) 次），再求第三大的（比 (n-3) 次），……如此一共比了次就可以完成此工作因此我们以 O(n2)，即在 n2 之层次来表此方法的计算量另外一种快排法，先把 n 个数分成若干小块，每块排好之后再合起来，则可以证明此种方法之计算量为 1 ，因排数字与排名字，号码相同，这种排法很有实用价值，例如某大城有一百万户，则 n2=1012，而 只有 2 x 107，其差别三个月与一分钟之比。
一般计算量的层次多以下表来区分，在上表中，k 为某一大于 2 的正整数，它们中间都有一道鸿沟，有基本层之不同，在计算器理论上，若某人能发现一个新的方法，降低一个层次的计算量，那么他的新方法有资格称之为一个突破，可以不朽矣表 1 有一个对上项各量之比较，是以计算器每秒作一百万次 (106) 计算为原则n n n2 n3 2n 3n n! 10 10-6 10-5 10-5 10-4 10-3 10-3 0.059 0.45 20 10-6 10-5 10-5 10-4 10-2 1(秒) 58(分) 1 年 50 10-5 10-4 10-4 0.0025 0.125 36 年 2 x 1010 年 1057 年1000 10-5 10-3 10-3 1 16 小时 10333 年 极大 极大106 10-5 1 6 1 月 105 年 极大 极大 极大109。