对于未公开分享的资源，如果你没有115 vip账号，则进入时会显示“文件拥有者未分享该文件”（如下图）

如何下载这样的文件呢？
以下载http://115.com/file/e7v75rws ，用浏览器Chrome为例：

1.打开你要下载的文件页面http://115.com/file/e7v75rws
2.确保你目前处于登录状态
3.在页面空白处右键点击“审查元素”
4.切换到Element页，在查找框内输入page_file_info进行查找，找到图中的几个变量

5.在地址栏输入 http://115.com/?ct=pickcode&ac=collect&user_id=AAAAA&tid=BBBBB&is_temp=CCCCC&aid=1&cid=0 这个链接，其中AAAAA由上图中变量user_id的值代替，BBBBB由file_id的值代替，CCCCC由is_temp的值代替
（如图中的地址即为 http://115.com/?ct=pickcode&ac=collect&user_id=3392596&tid=27775755&is_temp=0&aid=1&cid=0）
6.若页面返回情况如下：

则说明你要下载的文件已经转存成功，且保存在你自己网盘的根目录下。前往自己的网盘即可完成下载。

对于超级大牛的八卦也是意外地有趣，所以特地转载来分享一下：

===============================转载分界线====================================

本组当然不能少了Knuth的八卦（本组的组名 “Fun with Computer Science” 就直接来自于 Knuth 2008 年圣诞树讲座（关于圣诞树讲座那又是另外一个八卦了（有人说程序员与非程序员最大的区别就是程序员喜欢使用嵌套的括号？（哈，我想Lisp程序员应该最有发言权）））的标题 ”Fun with ZDDs“），所以特转来一些，虽然都比较old了，但是偶尔回味一下也不禁捧腹。

这一组八卦在网上流传甚广，但源头应该是来自于水木清华BBS，原作者为hellooo（又看到有人说这个hellooo实际是个机器人？）。如果看过一本小册子“Mathematical Writing” 的话就会发现下面所有的段子都是从其中翻译过来的，所以推荐8g爱好人士如果没看过的可以去看一下，网上有电子版下载的。该册子还记录了其它好多有趣的东西，比如里面提到，Knuth写"Surreal Number"时，只用了一个星期就搞定了，这效率实在是太惊人了。说到效率又想到昨天刚看到的一个事情，话说约翰.卡马克写程序是公认的令人发指的快，这厮最近也twitter了，某天早上他发了一推，说今天的目标是先搞定一个Photo Mapping，再与原来RT的结果比较一下，于是马上有就好事者问：那你下午又准备干点啥？

好了，正式开始：
--------------------------------------------------------------

现在我开始当娱乐记者 ：）
从今天开始 8g Knuth 老爹

传说 Knuth 写书写文章的第一稿都是用铅笔写的。
很多人不明白他为什么不用键盘。
其实原因是这样，Knuth 曾经参加过一个训练小秘的学习班，
练习打字每分钟 80 个词以上。

到了后来，他发现他打字的速度大大高于他思考的速度，
所以如果他用键盘，就会出现很多停顿。
所以他决定用铅笔，这样可以与读者的思考速度保持一致。

标 题: 八卦 Knuth (2)

Knuth 作为一个计算机科学家，
为什么放下他所有的工作10年，
专心研究排版美学，创造 TeX 系统。
这是很奇怪的一件事情。

其实原因是这样。真正完美的数学排版应该是用金属活字进行的。
但是自从70年代以来，真正懂得这项技术的人都死光了。
新的排版机器，很不幸的都被计算机操纵了 (想想 Matrix )

虽然当时计算机能够排出一些简单的报纸，杂志，
但是它们不能很好的处理数学公式。

Knuth 想写出一个小玩艺儿能够在不同的计算机上制造漂亮的数学公式，
于是 TeX (读作 Tech(nology) 的前半部分) 就诞生了。

标 题: 八卦 Knuth (3)

很多人都对 TeX 断行的算法感到满意，
其实只有 Knuth 觉得担心。

他设计 TeX 的时候听说有一本书叫做 Aesthetic Measures，
作者是美国 No.1 数学家 George David Birkhoff。
是说怎样用数学公式来衡量“美”。

他查阅了7个Harvard图书馆，其中有一个图书馆有一个拷贝，
但是却被人借走了。无奈，跑到 MIT 去借。

还好，借到了。后来他就在 TeX 里加入了一个变量叫做 badness,
用来衡量一行文字的美感。badness 越小这行文字就越美。

但是与 Birkhoff 不同，Knuth 对这个公式没有多少信心。
也许是因为谦虚。

标 题: 八卦 Knuth (4)

Knuth 的书都是自己用 TeX 排版的，但是却不都是自己设计的。

传说 Knuth 和 Graham, Patashnik 合作写 Concrete Mathmatics 的时候
请了一位有名的图书版面设计家为他们设计好了书的尺寸，字体大小，标题样式，
后来 Hermann Zapf 专门设计了一种数学字体叫做 Euler,
自此，数学家 Euler 的灵魂浮游于 CM 当中……

另外一个图书设计家告诉 Knuth 一种格式数学公式的办法，
就是不把数学居中，而是只相对正文缩进一定距离。

标 题: 八卦 Knuth (5)

大家都知道 1974 年图灵奖授予 Knuth
主要是因为他写了一部巨著叫做
The Art of Computer Programming

但是不幸的是，很多人不能理解，甚至不相信
他为这部书起了这么一个不“科学”的名字。

后来很多人的著作里出现这样的文献引用：

"The Act of Computer Programming, Donald Knuth."

--
You will be a winner today. Pick a fight with a four-year-old.

标 题: 八卦 Knuth (6)

Knuth 是个喜欢自夸的人，这是毫无疑问的。
在他出版 The Art of Computer Programming 之前就已经有这种苗头了。

还没有出版的时候，在一次会议上，有个人知道他的这种性格，
就说：“我猜你正在写的这本书的书名肯定是 ‘An Introduction to Don Knuth’。”

Knuth 回答说：“正好相反。我要以你的名字来命名它。”

原来这个人的名字叫 "Art Evans".

标 题: 八卦 Knuth (7)

Knuth 是Caltech数学系博士毕业的
但是他常常说：“我戴着一顶计算机科学家的帽子，而不是一顶数学家的帽子。”

这说明他似乎对数学家有某些看法。
在他看来数学家只知道“What is it”，
而他还知道 "How to do it".
这就是他认为的数学与计算机科学的区别。

标 题: 八卦 Knuth (

Knuth 回到 Stanford 时，学校让他自己给自己一个头衔

他就选了一个
Professor Emeritus of The Art of Computer Programming

他其实觉得“计算机科学”不是科学。
虽然大家很希望计算机编程变成科学，这是某ACM刊物提出的忠旨。
但是 Knuth 觉得奇怪为什么大家这么喜欢科学，
以致于他们瞬间把程序设计变成了科学，方法就是叫它“计算机科学”。

-- Just call it "Computer Science"

在他眼里，计算机科学其实仍然是门艺术。

标 题: 八卦 Knuth (9)

在 Knuth 的眼里，科学与艺术有什么区别呢？
艺术是人创造的，而科学不是。
艺术永远是可以无止境的提高的，而科学不是。
艺术需要天赋才能掌握，而科学不需要，按部就班就行。

所以，The ... ART ... of Computer Programming!

标 题: 八卦 Knuth (10)

Knuth 的 The Art ... ft，这么长……以后简称TAOCP吧

…… 开始写的也不那么好。

传说有一天 Bob Floyd 给 Knuth 一封信，开门见山就说：
“Don, 请不要用那么多感叹号！”信的结尾至少打了五个概叹号。

看了之后，Knuth 发现 TAOCP 里竟然平均每页有两个感叹号！！

标 题: 八卦 Knuth (11)

有人说 Knuth 写完三卷 taocp 就去研究 TeX，其实是因为害怕写第四卷。
很多人早就希望他放下 TeX，继续写书。
Knuth 说：“一个人要把事情做的完美，只有当他跟上帝的意图保持和谐，
现在上帝要我去写第四卷了。”

标 题: 八卦 Knuth (12)

Knuth 很推崇随机算法。
他批改作业时，一般都是翻到随机一页，仔细看那一页，
之后就对学生的作业有了一个概貌，其它的部分就看的不那么仔细了。

Knuth 看书的时候首先看第316页，如果书很短就看第100页。
仔细看那一页。之后他就可以说那本书好不好。
据说这样做出判断的正确率很高。

不知道是否有很多人跟他学，看316和100.
以后写书要注意把第316页或者100页写好呀！

标 题: 八卦 Knuth (13)

继续八卦

你们知道 Knuth 发明了一种程序设计方法叫做 Literate Programming (文学编程)
把程序当成文学作品来写。这样可以创造永恒的作品，
甚至几十年后还有人用它作为茶余饭后的读物。

他为什么要发明这个东西。原因有2:

1. 他想让一个程序员（也许是他自己）在某一天拿到普利策奖。
2. 他想让提出“Structured Programming”(结构化程序)的那些家伙
在写“非文学程序”的时候，就像他当年写“非结构化程序”
的时候一样觉得自己有罪。

他的“文学编程”思想最早是在英国 Computer Journal 发表的。
当人问他为什么不在美国发表。
他说，美国人没文化，他们不能理解这个东西。

标 题: 八卦 Knuth (14)

今天写点有用的8g

Knuth 喜欢在他的作品里用 "we" 作为主语，
虽然很多时候文章是他一个人写的。

有人认为使用被动语态好。但是 Knuth 认为不应该大量使用被动语态。
“用 We 可以减少被动语态带来的麻烦。‘we’是指你和你的读者。”
那么怎么称呼作者？答案是: the authors, the first author, 或者直接用名字。

但是他确实反对使用 "I"，除非你是身名显赫，
人人尊敬的君王式人物，否则最好不要在论文里用 "I"。

在你描述你的程序时，喜欢说 "we insert the element in the heap"
还是 "it inserts the element in the heap" ?
Knuth 总是喜欢用 "we"。显然他已经融于算法的动作之中了。

标 题: 八卦 Knuth (15)

虽然他不喜欢论文里用 "I", 但是他喜欢让他的程序自称 "I".

看这里：

This is TeX, Version 3.14159 (Web2C 7.3.7x)
! I can't find file `kkkk.tex'.
<*> kkkk.tex

Please type another input file name:

有很多人跟着他学，把这种称呼顽皮的发挥到极致：

Welcome to Scheme 48 0.57 (made by wy on 日 11月 24 13:20:27 CST 2002).
Copyright (c) 1993-2001 by Richard Kelsey and Jonathan Rees.
Please report bugs to [email]scheme-48-bugs@martigny.ai.mit.edu[/email].
Type ,? (comma question-mark) for help.
> (define (sq x) (* x
x))

; no values returned
>
Exit Scheme 48 (y/n)? <按 Ctrl-D>
I'll only ask another 100 times.
Exit Scheme 48 (y/n)?
I'll only ask another 99 times.
Exit Scheme 48 (y/n)?
I'll only ask another 98 times.
Exit Scheme 48 (y/n)?
I'll only ask another 97 times.
Exit Scheme 48 (y/n)?
I'll only ask another 96 times.
Exit Scheme 48 (y/n)?
I'll only ask another 95 times.
Exit Scheme 48 (y/n)?
I'll only ask another 94 times.
Exit Scheme 48 (y/n)?
......
标 题: 八卦 Knuth (16)

Knuth 有一次布置了一个作业，要求在两个星期以内做出一个
用于控制时代广场那种 8x256 像素的阵列显示屏幕的系统，
并且写出一个用户手册。这个用户手册必须让不懂电脑的人也能看懂。

作业交上来以后 Knuth 把文档拿给他夫人(Jill Knuth)看，
结果发现 Jill 对文档里的 "Menu" 和 "Scrolling" 这样的单词都摸不着头脑，
更不要说 "left-indented", "exit", ...

标 题: 八卦 Knuth (17)

Knuth 曾经在 American Mathematical Monthly 发表过一篇
叫做 "The Toilet Paper Problem" 的论文，
据说是一个研究怎样合理使用厕纸的算法。

现在收录于 Selected Papers on Analysis of Algorithms, p.111
可惜清华图书馆没有。谁找到copy我一份。呵呵。

这篇论文投到 Monthly 时，在节标题使用了大量“粪便学”词汇。
编辑警告 Knuth 说，笑话在我们这里是危险的，请你三思！

不得已啊，Knuth 后来把小节标题里的那种词改掉了。
可是他很不想改文章的标题。
怎么办呢？
他给编辑一封信说，我已经以这个标题做过两次演讲，
这个主题已经被广泛的采用和讨论……云云。

最后编辑回信说：“你的厕纸被接受了！”

====================================
P.S. 附录：增加这篇论文的信息：

Stanford 计算机科学系楼里的厕纸架上可以并排放两筒厕纸。
人上厕所时有可能从两个中的一个取纸。

两个卷筒不一样大的时候，喜欢从大的那筒拿纸的人叫做 big-chooser
喜欢从小的那筒拿纸的人叫做 little-chooser。

如果两筒大小差不多，一般人都会从离自己最近的那筒取纸。

厕纸用完的时候一般由janitor(门口老大爷？)提供新的纸。
如果一边的用完了，那就换掉那一边，
如果两边同时用完，那么有人就有麻烦了……（我怀疑Knuth遇到了那么一次

我没仔细看完。
Knuth 似乎在计算那种两筒同时用完的窘境出现的概率……

论文原文的一个拷贝在：
[url]http://learn.tsinghua.edu.cn/homepage/015450/doc/toiletPaperProblem.pdf[/

url]

比较复杂的数学…… 有兴趣的可以看看。

另外，Don Norman 在这里有一些新设计的厕纸筒可以避免这种情况发生：

http://www.jnd.org/dn.mss/ToiletPaperAlgorithms.html

看来 Knuth 是在白费工夫。应该授予 IgNobel 或者 IgFields

标 题: 八卦 Knuth (1 8）

Knuth 和 Graham 他们合写的 Concrete Mathematics 本来
不会做的那么花哨的。

结果后来他们专门为那本书设计了字体，页面样式，
所有习题都给出了出处。几乎所有页面都至少有一个涂鸦，
连《爱利丝漫游奇境记》都被列入参考文献……

这是怎么回事呢？原因就是 Knuth 在写书期间去看了一部电影：
“白雪公主与七个小矮人”。

看完之后 Knuth 感叹道：
难以置信，这样完美的艺术品竟然可以在1937年完成。
我一定要把我的书做成一个艺术品，而且要在三个月之内完成！

结果他说到做到了。

在论文里，会经常看到诸如“该问题是一个NPC问题”“该问题是一个NP-Hard问题”的描述。

通过这两条可以看到，对P、NP、NPC、NP-Hard这些概念有些了解还是很重要的呀！

特地挑选了自己认为讲得最清楚明白的文章转来，希望能对还未了解的同学有所帮助。

作者为大名鼎鼎的Matrix67，写于他初中升高中那年

如果实在是嫌文章有些长的话，可以直接点这里跳到最后，有自己做的简短总结

==========================================================

你会经常看到网上出现“这怎么做，这不是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、输入2、输入3分别为True、True、False或False、True、False时，输出为True。
有输出无论如何都不可能为True的逻辑电路吗？有。下面就是一个简单的例子。

上面这个逻辑电路中，无论输入是什么，输出都是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问题还有许多有趣的东西，有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的，至少是不要把概念弄混淆了。

==============================================================、

个人总结：

课正好讲到最小生成树，提到了那个著名的Kruskal算法，令人不禁想到早前看到的一则扑克牌小游戏

于是就再次转过来应景一下。最早出处是哪我已经记不得了，大概是在松鼠会第一次看到的吧

==========================================================================

很多人都应该熟悉Kruskal算法吧，Joseph Kruskal正是这一个算法的发明者。

而下面的魔术，则与Joseph Kruskal的哥哥，美国著名的应用数学家Martin David Kruskal有关。

如果你的朋友告诉你，他今天要跟你打个赌：他首先把一副扑克牌洗好，把除了两个王以外的52张牌依次扣在桌面上，然后他把第二张牌翻开，是方片5，他向前数5张牌，翻开后，是梅花4，然后又向前数了4张牌，以此类推，每一次翻开的牌上面的数字是几，就向前走几步（J,Q,K按1算）……最后，当翻开红桃5时，已经接近牌的末尾，无法再向前数了。

接着，他把除了最后翻开的红桃5以外的所有牌都翻回去。

然后，同你讲“你可以从第一张牌到第十张牌任意选一张开始，然后重复我的过程，如果你最后的一张牌也停在红桃5，那么你就输了，要给我100元；如果你的最后一张不是红桃5，我就输了，给你100元”。你敢跟你的朋友打这个赌吗？ 
你可能会想，最后一张牌停在哪个位置有很多种可能性，最起码倒数的十张牌都要可能，估计不会这么巧，我的最后的一张牌正好和我朋友的完全一样，十有八九一百元钱归我了。但是实际情况是，你的朋友是聪明的，十有八九要输的不是他，而是你。关于这个游戏的概率计算结果会令你大吃一惊。 

我们先来看一个例子，假设你选了从第一张牌开始，是梅花Q,按照规则向前走一步。

第二张是方片5，你的朋友刚刚翻过的，到这里，你应该猜得到，游戏不需要再进行下去了，你已经输了，因为在这之后，你会完全重复你朋友翻牌的路径，最后也终止于红桃5。你或许会说，我应该不会这么不幸吧，我翻开的第二张牌正正好好是我朋友翻过的。要是我不从第一张牌开始，从第三张牌、第四张牌、第十张牌开始，情况还会这么糟吗？是的，你翻开的第二张牌不是你朋友翻过的牌的可能性还是很大的，可是以后向前翻牌的过程中只要有任意一张在你朋友走过的路径上，你就输定了。尽管对于翻开的某一个单张牌“中招”的概率不是很大，可是连续翻很多张牌都不“中招”就并非易事了。只有在整个过程中左夺右闪，小心翼翼，不掉进你朋友“设下的所有陷阱”，你才有可能赢得这个赌局。 

我们可以粗略估计一下你取胜的可能性。 

首先，由于J,Q,K都按1算，52张牌的数字平均大小小于5，暂且按5计算，那么你从头走到尾，平均要翻10张牌； 

然后，对于这十张牌，每一张的数字可能为1到10十种可能性，如果这张牌的数字“大小合适”，翻开的下一张牌就会落入朋友的陷阱,按照这张牌前面十张牌中平均只有一张是你朋友翻过的算（实际因为有很多张“1”，十张牌中会出现多于一张的“危险牌”），那么你一次生还的概率是9/10。 

最后，你久经考验、到了最后一张牌仍然和你朋友的红桃5不重合的可能性就是9/10的10次方，只有35%。而如果考虑了“1”牌的因素，用更精确的方法计算的结果为15%左右，你朋友在这场赌局中有85%获胜概率。也就是说，你的最后一张牌和你朋友的最后一张牌在大多数情况下会是一样的。

由于一副扑克牌只有52张牌，如果把这个游戏当作魔术进行表演的话，仍然有百分之十几的失手机会，但是如果用两副、三副或更多扑克牌，失败的可能性会降至很低（两副扑克牌就可以降至5%）。除了用扑克，魔术师还可以要求你在长长的一篇英语文章中，从一个单词开始，看这个单词有几个字母组成就向前越过几个单词，以此类推，一直到文章的末尾，然后魔术师会表演他的“读心术”说出你停在的最后一个单词。 

与这个纸牌游戏类似的一种用于破解密码的计算机算法称作波利德袋鼠算法。这个算法中，两个数字的链条，被称为“两只袋鼠”，在解空间里面各自“跳跃”，其中一只为“驯化的袋鼠”，相当于你的朋友，它的参数都是确定的，而另一只为“野生的袋鼠”，相当于你，算法希望得到“野生的袋鼠”的参数。驯化袋鼠每次跳跃之后都会做一个陷阱，如果野生袋鼠的某次跳跃碰到了这个陷阱，则表明他们的参数是一致的。这样，就可以使用驯化袋鼠的参数来推导出野生袋鼠的参数，与纸牌游戏整个过程非常相似。