什么是 P 和 NP
在大O那里看过，输入一变大，活儿会膨胀多少。可有些问题，输入只要稍微大一点，要考虑的情况数就会爆炸。所以到现在，还没有人知道快速的解法。奇妙的是，自己找答案很难，可要检查别人给的答案对不对，却一下子就行。
情况数爆炸
假设一个人要把几座城市都走一遍，每座只去一次，还想找出最短的路。
只有三座城市时，走的顺序没几种。可城市一座座加上去，要考虑的顺序数转眼就多得吓人。
用下面的按钮加城市试试。
城市一多，走的顺序数就爆炸。（城市 +1 → 情况数成倍增加）
每多一座城市，顺序数就成倍地涨。这就是在大O里看过的“爆炸式增长”。
城市只要十几座，顺序就多到一个个去试的办法很快就走不通了。
难解，但好验证
不过有一点很有意思：找答案很难，可要是有人拿来一个答案，验证它对不对却很快。
想想数独。把空格都填满很伤脑筋，可要检查一张填好的盘面是否合规则，用眼睛扫一遍就完了。
点一个候选答案，马上就能验证完。（找很难 · 查一眼就行）
难找，好验证。这两件事各走各的，正是这类问题的特点。
旅行商问题也一样。找最短的路很难，可如果问的是“有没有总距离不超过多少的路”，只要把别人给的那条路的距离加一加，就能确认。
有快速的解法吗
这里冒出一个大问题：“验证快的问题，解起来也快吗？”
也许只是我们还没找到聪明的办法，也许真的就没有快速的解法。
在下面点开两种立场看看。
点开两种立场看看。（验证快 = 解起来也快？ · 还没人知道）
令人吃惊的是，这个问题至今没人知道答案。全世界的数学家和科学家钻研了很久，“有快速解法”和“没有”都没能证明。
这是计算机科学里最有名的未解问题。所以要是有人说“这很简单”，不妨稍微怀疑一下。
这个问题叫作“P 对 NP”。关键在于，它至今仍是一个没有解决的问题。
难题们
这样的问题不止一个：走遍许多城市的最短路线，在重量限制内挑出最值钱货物的背包，让相邻国家颜色不重复地给地图上色。
表面上各不相同，内里却很像：情况数会爆炸，而验证很容易。
在下面切换例子看看。
点例子来切换。（旅行商 · 背包 · 图着色，都是同一类难）
像这样相似的问题，已经汇集了好几千个。奇妙的是，只要其中任何一个找到了快速解法，其余的也都能快速解决。
可以说它们手拉着手。解出一个就全解出来了，这才更有意思。
总结
归成一句话：有些问题输入稍微一大，情况数就爆炸，所以至今还不知道快速的解法。
可是，找答案虽难，验证往往很容易。那么，验证快的话，解起来也快吗？这还是个没人知道的大谜题。
在下面按顺序点开来总结。
按顺序点要点来总结。（爆炸 → 验证容易 → 仍未解决）
不是所有问题都一样容易，有的问题真的很难对付。
可难对付并不等于没办法。下一课，我们会遇到一些聪明的办法：放弃完美的答案，转而快速找到“足够好的答案”。