有没有解不快的问题?

情况数会爆炸

一个人要把好几座城
每座都走一遍。
想找最短的路。
三座城时
走法没几种。
可一座座加上去，
要查的走法数
一眨眼就大得吓人。
用下面的按钮加城。

加一座城，走法的数目就爆。(城 +1 → 情况数相乘)

每加一座城，
走法就按乘法涨。
这正是大O里见过的
“爆炸式增长”。
只要十几座城，
走法就多得
一个个查的路
很快就堵死了。

解起来难，验起来易

不过有个有趣的地方。
找答案也许难，
可只要有人把答案拿来，
验它对不对就很快。
想想数独。
把空格全填上很费脑筋。
但拿一张填好的盘，
照规则检查它，
用眼睛扫一遍就完了。

点一个答案候选，验起来很快。(找很难 · 检查一眼就行)

找起来难，
验起来易。
这两件事各走各的，
正是这类问题的特点。
推销员的路也一样。
找最短的那条难，
但量一条给定的路、
算“这条路一共多长”，
只要加几次就行。

有没有快的解法?

这里冒出一个大问题。
“验得快的问题，
是不是解也快?”
也许只是我们还没
找到聪明的办法。
也许，是真的
根本没有快的解法。
在下面点点这两种立场。

点点这两种立场。(验得快 = 解也快? · 还没人知道)

令人吃惊的是，这个问题
至今没人知道答案。
全世界的数学家和科学家
钻研了很久，
可“有快解法”
和“没有”都没能证明。
这是计算机科学里
最有名的未解之题。
所以谁要说“很容易”，
你不妨稍微怀疑一下。

几个难题

这类问题不止一个。
把许多城走得最短的路，
在重量上限内
挑最值钱那堆货的背包，
给地图上色、
让挨着的国家不同色。
表面看各不一样，
往里看却很像。
情况数会爆，
而验起来容易。
在下面换换例子。

点一下换例子。(推销员 · 背包 · 地图上色 — 都是同一种难)

这样相像的问题
聚了好几百个。
奇妙的是，只要其中一个
被找到快的解法，
其余的也都快了。
它们彼此手拉着手。
所以更耐人寻味。
解开一个，就解开全部。

总结

用一行收一收。
有些问题，输入只大一点点
情况数就爆，
所以还没人知道快的解法。
可找答案难，
验答案却常常容易。
那么验得快，解也快吗?
这个至今谁也不知道，
是个大谜。
在下面依次点点来收尾。

依次点要点来收尾。(爆炸 → 验起来易 → 仍未解)

不是每个问题都一样容易。
有些是真的难缠。
但难缠不是终点。
下回的故事里，
我们会遇到一些聪明办法：
放弃完美的答案，
转而很快地找到
一个“够好”的答案。