2006-08-28 22:58| 
77 Comments | 本文内容遵从 这或许是众多OIer最大的误区之一。
你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题，NPC问题才是。好，行了，基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。接下来你可以看到，把NP问题当成是 NPC问题是一个多大的错误。
还是先用几句话简单说明一下时间复杂度。时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。不会存在O(2*n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此，我们会说，一个O(0.01*n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。
容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者：一种是O(1),O(log(n)),O(n^a)等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。
自然地，人们会想到一个问题：会不会所有的问题都可以找到复杂度为多项式级的算法呢？很遗憾，答案是否定的。有些问题甚至根本不可能找到一个正确的算法来，这称之为“不可解问题”(Undecidable Decision Problem)。The Halting Problem就是一个著名的不可解问题，在我的Blog上有过专门的介绍和证明。再比如，输出从1到n这n个数的全排列。不管你用什么方法，你的复杂度都是阶乘级，因为你总得用阶乘级的时间打印出结果来。有人说，这样的“问题”不是一个“正规”的问题，正规的问题是让程序解决一个问题，输出一个“YES”或“NO”（这被称为判定性问题），或者一个什么什么的最优值（这被称为最优化问题）。那么，根据这个定义，我也能举出一个不大可能会有多项式级算法的问题来：Hamilton回路。问题是这样的：给你一个图，问你能否找到一条经过每个顶点一次且恰好一次（不遗漏也不重复）最后又走回来的路（满足这个条件的路径叫做Hamilton回路）。这个问题现在还没有找到多项式级的算法。事实上，这个问题就是我们后面要说的NPC问题。
下面引入P类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项式的第一个字母。哪些问题是P类问题呢？通常NOI和NOIP不会出不属于P类问题的题目。我们常见到的一些信息奥赛的题目都是P问题。道理很简单，一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。
接下来引入NP问题的概念。这个就有点难理解了，或者说容易理解错误。在这里强调（回到我竭力想澄清的误区上），NP问题不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。比方说，我RP很好，在程序中需要枚举时，我可以一猜一个准。现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？我说，我RP很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，嘿，神了，路径长度98，比100小。于是答案出来了，存在比100小的路径。别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100 小的解。在这个题中，找一个解很困难，但验证一个解很容易。验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么，只要我RP好，猜得准，我一定能在多项式的时间里解决这个问题。我猜到的方案总是最优的，不满足题意的方案也不会来骗我去选它。这就是NP问题。当然有不是NP问题的问题，即你猜到了解但是没用，因为你不能在多项式的时间里去验证它。下面我要举的例子是一个经典的例子，它指出了一个目前还没有办法在多项式的时间里验证一个解的问题。很显然，前面所说的Hamilton回路是NP问题，因为验证一条路是否恰好经过了每一个顶点非常容易。但我要把问题换成这样：试问一个图中是否不存在Hamilton回路。这样问题就没法在多项式的时间里进行验证了，因为除非你试过所有的路，否则你不敢断定它“没有Hamilton回路”。
之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白，信息学中的号称最困难的问题——“NP问题”，实际上是在探讨NP问题与P类问题的关系。
很显然，所有的P类问题都是NP问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。关键是，人们想知道，是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中，把所有 NP问题划进另一个集合NP中，那么，显然有P属于NP。现在，所有对NP问题的研究都集中在一个问题上，即究竟是否有P=NP？通常所谓的“NP问题”，其实就一句话：证明或推翻P=NP。
NP问题一直都是信息学的巅峰。巅峰，意即很引人注目但难以解决。在信息学研究中，这是一个耗费了很多时间和精力也没有解决的终极问题，好比物理学中的大统一和数学中的歌德巴赫猜想等。
目前为止这个问题还“啃不动”。但是，一个总的趋势、一个大方向是有的。人们普遍认为，P=NP不成立，也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的，就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题，也即所谓的 NPC问题。C是英文单词“完全”的第一个字母。正是NPC问题的存在，使人们相信P≠NP。下文将花大量篇幅介绍NPC问题，你从中可以体会到NPC问题使P=NP变得多么不可思议。
为了说明NPC问题，我们先引入一个概念——约化(Reducibility，有的资料上叫“归约”)。
简单地说，一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以约化为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题，两个问题就等价了。同样地，我们可以说，Hamilton回路可以约化为TSP问题(Travelling Salesman Problem，旅行商问题)：在Hamilton回路问题中，两点相连即这两点距离为0，两点不直接相连则令其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。
“问题A可约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。这很容易理解。既然问题A能用问题B来解决，倘若B的时间复杂度比A的时间复杂度还低了，那A的算法就可以改进为B的算法，两者的时间复杂度还是相同。正如解一元二次方程比解一元一次方程难，因为解决前者的方法可以用来解决后者。
很显然，约化具有一项重要的性质：约化具有传递性。如果问题A可约化为问题B，问题B可约化为问题C，则问题A一定可约化为问题C。这个道理非常简单，就不必阐述了。
现在再来说一下约化的标准概念就不难理解了：如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可约化为问题B。
当然，我们所说的“可约化”是指的可“多项式地”约化(Polynomial-time Reducible)，即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。
好了，从约化的定义中我们看到，一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题，联想起约化的传递性，自然地，我们会想问，如果不断地约化上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的 NP问题的这样一个超级NP问题？答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC 问题，也就是NP-完全问题。NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信，NPC问题是最复杂的问题。再次回到全文开头，我们可以看到，人们想表达一个问题不存在多项式的高效算法时应该说它“属于NPC问题”。此时，我的目的终于达到了，我已经把NP问题和NPC问题区别开了。到此为止，本文已经写了近5000字了，我佩服你还能看到这里来，同时也佩服一下自己能写到这里来。
NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。证明一个问题是 NPC问题也很简单。先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它（由约化的传递性，则NPC问题定义的第二条也得以满足；至于第一个NPC问题是怎么来的，下文将介绍），这样就可以说它是NPC问题了。
既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P 了。因此，给NPC找一个多项式算法太不可思议了。因此，前文才说，“正是NPC问题的存在，使人们相信P≠NP”。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。
顺便讲一下NP-Hard问题。NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广）。NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。
不要以为NPC问题是一纸空谈。NPC问题是存在的。确实有这么一个非常具体的问题属于NPC问题。下文即将介绍它。
下文即将介绍逻辑电路问题。这是第一个NPC问题。其它的NPC问题都是由这个问题约化而来的。因此，逻辑电路问题是NPC类问题的“鼻祖”。
逻辑电路问题是指的这样一个问题：给定一个逻辑电路，问是否存在一种输入使输出为True。
什么叫做逻辑电路呢？一个逻辑电路由若干个输入，一个输出，若干“逻辑门”和密密麻麻的线组成。看下面一例，不需要解释你马上就明白了。
┌───┐
│ 输入1├─→┐ ┌──┐
└───┘ └─→┤ │
│ or ├→─┐
┌───┐ ┌─→┤ │ │ ┌──┐
│ 输入2├─→┤ └──┘ └─→┤ │
└───┘ │ ┌─→┤AND ├──→输出
└────────┘┌→┤ │
┌───┐ ┌──┐ │ └──┘
│ 输入3├─→┤ NOT├─→────┘
└───┘ └──┘
这是个较简单的逻辑电路，当输入1、输入2、输入3分别为True、True、False或False、True、False时，输出为True。
有输出无论如何都不可能为True的逻辑电路吗？有。下面就是一个简单的例子。
┌───┐
│输入1 ├→─┐ ┌──┐
└───┘ └─→┤ │
│AND ├─→┐
┌─→┤ │ │
│ └──┘ │ ┌──┐
│ └→┤ │
┌───┐ │ │AND ├─→输出
│输入2 ├→─┤ ┌──┐ ┌→┤ │
└───┘ └→┤NOT ├→──┘ └──┘
└──┘
上面这个逻辑电路中，无论输入是什么，输出都是False。我们就说，这个逻辑电路不存在使输出为True的一组输入。
回到上文，给定一个逻辑电路，问是否存在一种输入使输出为True，这即逻辑电路问题。
逻辑电路问题属于NPC问题。这是有严格证明的。它显然属于NP问题，并且可以直接证明所有的NP问题都可以约化到它（不要以为NP问题有无穷多个将给证明造成不可逾越的困难）。证明过程相当复杂，其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些 0和1的运算），因此对于一个NP问题来说，问题转化为了求出满足结果为True的一个输入（即一个可行解）。
有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来，Hamilton 回路成了NPC问题，TSP问题也成了NPC问题。现在被证明是NPC问题的有很多，任何一个找到了多项式算法的话所有的NP问题都可以完美解决了。因此说，正是因为NPC问题的存在，P=NP变得难以置信。P=NP问题还有许多有趣的东西，有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的，至少是不要把概念弄混淆了。
Matrix67原创
转载请注明出处
77 条回复
您也随便说几句吧：
牛啊，博主不是一般的牛
能把比较复杂的东西表达的非常清晰非常条理，真不简单
感谢楼主,总算明白这三个东西了
很牛的楼主，可以将问题表述的如此有条理和清晰；坚持不懈，中国将出现另外一个大家，建议学习“自然语言处理”（AI范畴）：）
Just 2 questions:
Does NP stand for Not-Polynomial?
What does OI mean?
http://isdox.com
回复：Non-deterministic Polynomial
Olympiad in Informatics
老哥你是干啥的啊。。。真佩服你在这么浮躁的年代还能耐的住来研究这些。
这句话:
再证明其中一个已知的NPC问题能约化到它.
应该是:
再证明其中一个已知的NP问题能约化到它吧?
回复：没写错，如果一个问题可以由某个npc问题归约得到，则所有的np问题都能归约到它
厉害!
受益匪浅! '匪'是贬义,这个词是褒义.是否存在一定的条件转换把贬义的字变成褒义词呢?.
我也文科的呀！
QQ121195036
Noip C语言提高组. 15353287（我的群）
请大家帮忙宣传！
看完了，感觉豁然开朗
我想看看地核下面是什么
[...] 很多人对量子计算机有所误解，认为它可以解决一切困难的数学问题。事实不是如此，量子计算机能解决的问题，也仅仅是一小部分特殊问题。计算机科学家已经证明了，传统计算机能够有效解决的所有问题，用量子计算机同样能够有效解决。但是，对于计算机科学领域里的一类非常重要的问题——NPC问题，量子计算机是无能为力的。虽然我们还没有真正证明量子计算机不能胜任，正如我们还无法证明P到底等不等于NP一样，但是无数失败的尝试表明，量子计算机在这类问题上比普通计算机好不到哪里去。（如果你第一次听说P、NP、NPC，那么我建议你看一看Matrix67的这篇文章）。我们称量子计算机能够有效解决的问题为BQP类问题，这几类问题之间的关系如下图： [...]
明白了。。
太牛了。。
恩，这是我迄今看到得讲的最清楚的的一篇文章啦
[...] 曾经看到过自动扫雷软件，当时我就在想，扫雷游戏是否有什么牛B的多项式算法。最近才看到，扫雷问题居然是一个NP完全问题，并且这个定理有一个简单、直观而又神奇的证明。在这里和大家分享一下整个证明过程。 首先，扫雷一定是NP问题，它显然可以在多项式的时间里验证一个解。接下来，我们需要把一个已知的NP完全问题归约到扫雷问题上去。我们将给出一种把逻辑电路问题归约到扫雷问题的方法，这样的话我们就可以利用扫雷问题解决逻辑电路问题，从而说明逻辑电路问题不比扫雷难。我们将把逻辑电路问题转换成一种对应的扫雷布局，就像画画一样把逻辑电路画在扫雷的棋盘上。如果你还不知道什么叫NP完全问题，什么叫逻辑电路问题，你可以看一看我的这篇文章。 [...]
到此一游
3周年考古～
支持！很清晰，没啥可说的了，我尽量把大牛写的每篇文章理解一下。
牛人，支持。偶然的机会到了你的博客，看了几篇文章（主要是计算机的），感觉真的是一篇比一篇好。
能加一下我的qq吗？以后有什么问题就能请教你了，呵呵
QQ:379004115
写的非常好 哲人的思考 常人的表达
很有趣。
佩服~今晚再细看一遍。大牛，您辛苦了，为人民服务啊。
牛，太牛了，终于搞明白了
牛，之前我做过一些启发是算法的问题，现在看这个无疑是总结性的提高。太牛了
细看一遍后，豁然开朗。。。
[...] 详见 什么是P问题、NP问题和NPC问题 [...]
强！很强！十分强！
NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
那么有什么问题是一次猜不中而需要多项式时间才能猜中的？
这个结果于2000年发表在Mathematical Intelligencer上，论文题目是Minesweeper is NP-complete，
link：http://blog.csdn.net/leetonven/archive/2008/11/14/3297520.aspx
谢谢了，讲得很清楚
佩服 虽然很长 但是说的很清楚
回11楼，我总结了一个 热力学第四定律:
解决NPC问题导致的熵的增加>P
（ps:前面几个分别为
零：AB热平衡且BC热平衡，则AC热平衡。一：能量守恒。二：熵增。三：达不到绝对零度。）
受用了 :-)
写作思路很清晰
NP问题是否能在多项式时间内求解呢？？
同行，和你一样喜欢研究别人不研究的东西，加个好友吧我QQ1025679612
挺相信NP不等于P的，否则怎么会那么巧上百个NPC问题都没有任何一个被找到有多项式算法。。。
请问这是哪个学科的？我怎么完全看不懂？
但我很感兴趣
大牛啊
写的清晰易懂，可见博主的内功是何等之深厚
收藏了，谢谢
真是功底雄厚！无比崇拜！
神人！
[...] 关于NP问题的学习 December 28, 2009 yousilin Leave a comment Go to comments 今天抽空看了一下NP,NPC问题相关的东西，感谢Matrix67的讲解，从中领悟了不少 http://www.matrix67.com/blog/archives/105 [...]
透彻，太有水平了。
不过要是能把规约化的方法也大致介绍一下就好了
据说被惠普的一个研究员证明了。这两天还在看这个命题，没想到今天上午就看到了被证明P！=NP 。。。
博主太強了。。。求邏輯電路NPC證明的資料
3楼的大牛……
于是你四年前的日志在今天成功的成为了很及时的重要科普……
[...] HP 的研究员 Vinay Deolalikar 宣称自己证明了 NP 问题，得出了 P≠NP 的结论。 P 是否等于 NP [...]
晕啊，看不懂
攀登这个信息学的巅峰是我们这一代的终极目标。
大哥你写的太棒了,膜拜！！太棒了
[...] 曾经看到过自动扫雷软件，当时我就在想，扫雷游戏是否有什么牛B的多项式算法。最近才看到，扫雷问题居然是一个NP完全问题，并且这个定理有一个简单、直观而又神奇的证明。在这里和大家分享一下整个证明过程。 首先，扫雷一定是NP问题，它显然可以在多项式的时间里验证一个解。接下来，我们需要把一个已知的NP完全问题归约到扫雷问题上去。我们将给出一种把逻辑电路问题归约到扫雷问题的方法，这样的话我们就可以利用扫雷问题解决逻辑电路问题，从而说明逻辑电路问题不比扫雷难。我们将把逻辑电路问题转换成一种对应的扫雷布局，就像画画一样把逻辑电路画在扫雷的棋盘上。如果你还不知道什么叫NP完全问题，什么叫逻辑电路问题，你可以看一看我的这篇文章。 [...]
我们教授级的老师都没讲清楚的问题,你居然能这么有条理易懂的把它讲完,佩服佩服
实在是不得不回一下帖。。。
高三就懂这些了，实在很佩服，而且讲的这么清楚。。。
作为同龄人，实在很惭愧。。。
楼主很牛！佩服佩服
楼主帮了大忙
NPC问题在时间复杂度上是否还有区别呢？所有的NPC都假定时间复杂度相同吗？
[...] FROM: 来自http://www.matrix67.com/blog/archives/105 [...]
兄弟，字体有点小。
现任oier努力学习
[...] 转自：http://www.matrix67.com/blog/archives/105 [...]
果然是大牛啊，说理透彻，深入浅出，佩服佩服
深入浅出
算法导论若能由lz润色下就好了
膜拜。。。。。。
"O(n^100)的复杂度小于O(1.01^n)的复杂度"——这个有没有写反啊？前者的增长速度要比后者快吧
相互抄袭
关于约化我可不可以这么理解
电路1 有三个输入
电路2 也有三个输入
对于使电路1输出为true的所有输入 电路2同样也输出true
并且也存在其他的输入使得电路2输出为true
那么电路2是电路1的一个约化
是这样理解么？
发现沙发竟然是文章出现一年之后的事！看来就是这一年里，博客成长了不少，招来不少读者啊。
我最近遇到一个寻找Hamilton回路的问题，图已经确定是一个完全三分图K3(5),就是分三组，每组5个顶点的。要回答两个问题，首先是要判断该图是否存在两条没有重叠边的Hamilton回路，然后把所有Hamilton回路找出来。
有什么好的建议吗？
Leonard M. Adleman话说这么个人提出了DNA computing，也许可以给H回路找到多项式级算法
太牛逼了，偶然搜到这篇文章，佩服至极。
第一次看到这么牛逼的文章 像是中科院的牛人
不得不顶一下
[...] matrix67大牛的blog今天三周年了~~这是他推出的三周年的精选回顾全是精华阿 看看下面的这些文章，谁能看出这是个文科生(传说中去北大中文系泡妞?!)原文的地址: http://www.matrix67.com/blog/archives/5581. 原创科普说明文：递归假期的一篇作文，叫我们写任一说明文。我把这篇作文发到了我的Blog上。这可能是我Blog最早的技术文章，它确定了我以后类似文章的写作风格。2. 非常奇妙的证明：图形必在格点之外翻译的cut-the-knot上的一篇文章。这是我所见到的最elegant的证明之一，在饭桌上提到证明问题时我经常会举这个例子。几个好友很早就开始阅读我的Blog，他们一致认为这是最令人难忘的一篇日志。3. 几个把平面几何问题的辅助线做到空间去的数学趣题也是翻译的cut-the-knot上的系列文章，当时觉得确实非常神奇。后来的学习发现，其实射影几何中有更多有趣的例子。4. 追溯羊与车：Monty Hall Dilemma问题的故事我们数学老师提到了Monty Hall问题，他的说法是错误的，因此才写下这篇文章。当时写这篇文章主要是给我的同学看，因为那时这个Blog几乎只有我们同学才上。5. 几个很强的数列这是我在The On-Line Encyclopedia of Integer Sequences找到的，非常强。不是经常有考什么数列找规律的么？从这里面随便挑一个来，不查数列百科全书的话别人几乎不可能找出规律来。6. 爱的方程式惊奇函数图像系列文章的第一辑。后来渐渐有了3D桃心函数、阴阳图函数、公式生成的色情图片等一系列的东西。7. 什么是P问题、NP问题和NPC问题这可能是我写的最长的一篇原创文章了。很多网友都说，在类似的文章中这一篇是讲解最清楚、最通俗易懂的。8. KMP算法详解可能是这个Blog最经典的文章了。不少朋友最初都是找KMP算法找到这个Blog来的。9. 位运算讲解系列文章应该是这个Blog里第二经典的文章了。10. 无限小却无限大的集合 & 阶梯状的连续函数前段时间我和一帮人在饭桌上提到了诡异的函数，比如处处连续处处不可导的函数、除常函数外没有最小正周期的周期函数、导数为正却找不出单增区间的函数、平面上任意小的范围内均能找到一点的单值函数、在有理点处处不连续在无理点处处连续的函数（俗称爆米花函数）。但处处连续的阶梯函数，很多人可能还是第一次听说。挺好玩的。11. 令人称奇的简单证明：五种方法证明根号2是无理数牛！这个牛！想看一些精妙的证明，体会到数学证明的神奇之处的话，从这里开始是一个不错的选择。12. 从零开始学算法：十种排序算法介绍（上）这个也牛！同样地，如果想看一些精妙的算法和复杂度的分析证明，体会CS的乐趣，从这里开始是一个不错的选择。13. 从零开始学算法：十种排序算法介绍（中）这篇日志里讲了快速排序的平均复杂度的分析和证明，很强大很科学。初学算法的人经常会忽略复杂度分析这一步，学过一段时间后回过头来看看经典算法的复杂度分析是很有益的。14. 从零开始学算法：十种排序算法介绍（下）没啥好介绍的……以后有些没什么特别背景的日志我就不附加文字介绍了，不然写着好累。15. 无题 于2007年5月16日现在我已经很少在自己的Blog里写我的感情生活了。这是我在19岁生日那天写的。16. 数论部分第一节：素数与素性测试17. 神奇的分形艺术（一）：无限长的曲线可能围住一块有限的面积分形艺术系列的开篇。分形这个东西其实挺好玩的。18. 十大另类程序语言（上）19. 十大另类程序语言（下）哈哈，这个好玩！！有几个语言相当搞笑，挺佩服老外的想象力的。20. 令人敬畏的十维空间出人意料的结论。对应的几何图像太难以想像了。我一直想写一篇描述四维几何形状的文章，至今仍未动键盘。21. 十个有趣的英文文字游戏（上）22. 十个有趣的英文文字游戏（下）很早就对英文文字游戏感兴趣，看到过不少，记了各种性质独特的英文句子。有一天突然想整理出来写一下，于是有了这两篇日志。中文其实也有很多好玩的东西，比如对联啊，灯谜啊，拆字啊，断句啊，回文句啊等等。23. 神奇的分形艺术（四）：Julia集和Mandelbrot集还是在饭桌上，每次提到数学神秘得令人恐惧时我都会讲起这个。真是太神奇了，一个如此简单的过程竟然可以生成这般复杂玄妙的分形图形。24. Tupper自我指涉公式：图象里竟然包含式子本身数学中的魔术，非常有意思。本以为非常神奇，揭秘之后恍然大悟——不过如此。25. 编辑距离、拼写检查与度量空间：一个有趣的数据结构26. Poincaré圆盘模型：一个神奇的双曲世界进北大时恰逢数学文化节十周年，数院开了一系列精彩的讲座。我去听了其中三个讲座，这是我听过的最精彩一次。看《什么是数学》时看到了相关的内容，再结合这里的一些东西仔细品味了一下，真是科学得无与伦比。以后我还将引用到这篇日志。27. 等高线模式：解决极大极小问题的另类策略Pólya的《数学与猜想》确实是一本好书。我在这本书里学到了好多东西，其中一个最主要的收获就是这套诡异的极大极小问题解决办法。28. 趣题：直觉 VS 理性思考 经典概率问题29. 另类搞笑：自我指涉例句不完全收集AboutMe里就提到，我喜欢带有递归和自我指涉的句子。一直收集着很多这样的句子，终于决定整理出来和大家分享。30. 物理方法解决数学问题（二）：Archimedes与球体积公式31. 趣题：n为奇数时，正n边形的三角形剖分内有且仅有一个锐角三角形从EagleFantasy那里挖来的，是我目前最喜欢的“一句话证明”。跟别人提到“一句话证明”时我必然会拿它当例子。32. 物理方法解决数学问题（四）：Fermat-Torricelli问题33. 证明实数区间不可数的新方法我喜欢讲课，喜欢听每次揭晓“谜底”后下面的人恍然大悟的感叹声，喜欢从基本结论出发一步步推出不可思议的结论。在所有科学的东西里，我最爱讲的，最具悬念，最有戏剧性，结论最令人惊讶，最能颠覆传统观念就是对无穷集合势的分析了。从有限到无限，从可数到不可数，以及直线和平面上的点一一对应等等，每一个证明都令人拍案叫绝。这里提到了实数区间不可数与博弈游戏的关系，从一个全新的角度来看连续统，分析证明过程实在巧妙。34. 趣题：一个与Hamilton回路有关的问题35. 100囚犯问题、100囚犯问题加强版与选择公理（上）36. 100囚犯问题、100囚犯问题加强版与选择公理（下）37. 趣题：构造函数使得平面上任意小的圆内均包含函数上的点有一天突发奇想，到豆瓣的数学小组去逛了一圈，然后发现了这个神奇的东西。38. 很诡异的博弈问题分析方法39. 趣题：猜帽子游戏与Hamming编码40. 趣题：构造游戏初始状态使得后行者必胜41. 物理方法解决数学问题（五）：一个与椭圆有关的性质42. 趣题：量子计算机、另类编程语言和幂函数的解释43. 趣题：对数字进行编码使其按字典序排列后仍然有序这两篇日志是相当科学的算法题。很长时间没看到这么经典有趣的题目了，特别是前面那篇。44. 神奇的锈规作图：单用一个只能画单位圆的圆规如何作等边三角形这个精彩，强烈推荐一下。45. 矩阵、随机化与分形图形某留学Stetson大学的MM一次在校内上发日志链接到了我的Blog，我回访回去时认识了她。我和Stetson MM网恋了一段时间，发国际短信花了我不少钱。后来Stetson MM有了男朋友了，这段故事就此告终。这告诉我们：建网站来吸引MM终究是不可靠的。Stetson MM是我所见过的最适合我的MM，其思维的相似程度达到了令人惊讶的地步，世界上居然有一个如此像我的异性真是不可思议！这篇日志与Stetson MM在线性代数课上的一个课题研究有关。Stetson MM告诉我，她一个同学看到这篇日志后问她我Blog里的Stetson MM是不是指的她，她惊呼“你也订阅了这个Blog”呀。Small world。当时这篇日志在抓虾上的推荐数很是让我吃惊。46. 分享一些有趣的面试智力题（上）47. 分享一些有趣的面试智力题（下）48. 20年的时间里你可以做些什么？今年我20岁生日时写下的一篇特别的日志。神奇的是，这篇日志的ID正好也是我的生日——516。49. 趣题：空间四边形外切于给定球，求证四切点共面50. 趣题：直尺不够长时如何作出连接两点的直线？《什么是数学》中与射影几何相关的一个习题。当时我曾经在古汉课上大叫“太科学了”。 M12 Puzzle 传Google2亿美元收购Digg [...]
[...] http://www.matrix67.com/blog/archives/105 （有例子的一篇中文介绍，感谢靖难兄推荐） [...]
谢谢博住，明天考试就考这个。:-)转走了
是不是说所有的NPC问题都可以互相约化？或者说是不是解决了一个NPC问题就相当于解决了所有的NPC问题？
大神，拜读了你这篇文章之后把NP，NPC这些概念一下子都弄懂了！！！感谢
算法考试有底了