从所有情况中找出绝对最优的组合永远是极其耗时的任务。对于这样的算法，类似D（2n）这样的时间复杂度并不罕见。但还有其他一些问题，看似可以在合理的时间内完成，实际却不是。
这些问题当中，比较著名的一个就是旅行商问题（Traveling Salesman Problem）。想象自己是一名负责很多客户的售货员——比如说客户数量是30，前面最佳歌曲问题的一半。为提高工作效率，你想在地图上找一条能把每个客户访问一次，且不会重复访问的最短路径。
要求给出旅行商问题的最优解，一种最有名的算法是O（n！）级的。那可是n的阶乘。另外有些耗时较短的算法能给出近似最短，但无法保证绝对最短的路径。对30个城市来说，使用这种O（n！）复杂度的算法需要执行30 ！个步骤，或者说265252859812191058636308480000000步。到1.5 GHz的处理器上运行看吧——在你有生之年是运行不完的。
真正严重的问题是：旅行商问题并不是人为搞出来的玩具题目。确实有人需要在全世界范围内规划最短路由。还有一些类似问题，从算法上考虑与旅行商问题如出一辙，比如规划机器人在厂房中的行走路线。这是个又大又难的问题。
计算机科学家把问题归为三大类：
许多问题，比如排序，可以用运行时间为多项式复杂度（比如O（n2））的算法解决，我们把这类问题称为P类问题（P代表“多项式”）。
另一些问题，比如求最优组合，存在已知的算法，但解法太大太难，即使中等规模的数据量都难以在合理的时间内解决。我们把这类问题称为难解型（intractable）问题。
还有另一些问题，如旅行商问题，看似难解，但可能存在P类解法，只是我们尚未发现。
我们把这类问题称为NP类问题。
理论计算机科学领域最大的未解问题之一就是证明要么NP和P完全不同（意味着我们永远不能在多项式时间内解决旅行商最短路径问题），要么P包含NP。
你可能疑惑，有关算法的问题可以“证明”吗？毕竟我们有这么多不同的编程语言和编写算法的不同方式。如何能确定地证明一件事情是可做或不可做的呢？然而，这的确可以。事实上，Alan Turing（阿兰?图灵）甚至证明了某些算法是编写不出来的。
在编写不出来的算法当中，最著名的一个是程序停止问题（Halting Problem）。我们编写过读取或输出其他程序的程序。可以想象，一个程序完全可以读取另一个程序并输出相关信息（比如此程序中有多少print语句）。那么，能否编写一个程序，输入另一个程序（比如通过文件），然后告诉我们那个程序会不会停止呢？考虑这样一种情况：输入程序中有一些复杂的while循环，导致我们难以判定while循环表达式会不会变成false。然后再想象一下这样一组循环相互嵌套的情况。
……
展开
