SEP：可计算性与复杂性（三） (2-2)

让我们将目光移向这张图的底部，其有一个区域被用绿色虚线标记出了“真正可行(truly feasible)”。注意，这不是一个数学上严格定义的类，而是一个直观的概念，对于所有那些合理大小的实例，在合理的时间量内，使用我们能承担得起的计算机，而能被准确解决的问题(有趣的是，这些年来随着计算机运算速度的急剧增长，我们对于我们能够处理多大实例，的相关期望，也相应地提高了。因此，什么是真正可行的边界的变化，比计算机运算速度的增加，显示得要慢)

就像前面所说的那样，P是一个很好的数学工具，涵盖了可行问题的集。在P中的有些问题，其问题大小n要求 ₙ¹⁰⁰⁰ 时间，因此是不可行的。“自然”在这里似乎成了我们的朋友，也就是说在 P中自然发生的那些问题倾向于相对简单的算法，及“自然”问题也往往是可行的。对于大小为n的问题所要求的步数，往往小于，有着较小乘法常量c与很小指数k的cnᵏ，即k ≤ 2。

实践中，关于自然发生问题的渐进复杂度(asymptotic complexity)，往往是决定它们是否可行的关键议题。对于有着复杂度17n的问题，在现代计算机中一分钟内就可解决，其每个实例大小为十亿。而另一方面，一个最坏情况复杂度为2ⁿ问题，即使其实例大小只有100也用尽我们一生的时光都无法被解决。

值得注意的是，自然问题往往是对于一些重要的复杂性类完全的，即图中那些类，而只有极少数是其他的。这个有趣的现象意味着，算法与复杂度将不仅仅是抽象概念，它们在实践层面也非常重要。我们在提供，关于我们感兴趣的问题对于一个著名的复杂性类是完全的，这个方面的证明上，已取得了瞩目的成功。如果该类被P所包含，那么我们通常可以查找一个已知能行的算法，否则，我们必须研究问题的简化与近似，这可能可行。

关于NP优化问题(NP optimization problems)的近似有着丰富的理论(见，(Arora & Barak, 2009))。例如，上文提到的子集和问题，是一个NP完全问题。更可能的是，它需要指数级时间去判定一个给定子集和问题是否有一个精确解。然而，如果我们仅仅想看看我们是否能达到给定位数的精度，那么这个问题就将变得非常简单，即，子集和问题很难，但去近似则很简单。

甚至，对递归可枚举完全的停机问题也有很多重要而可行的子问题。给定一个程序，它总的来说不可能知道它自己在干什么以及其最终是否停机。然而，多数被程序员与学生写下的程序都可被现代的编译器与模型检查器，自动地分析，优化，甚至修正。

NP类在实践与哲学上都非常重要。它是这样的问题类S，其中，任意输入ω，在S中，当且仅当，存在证明P(ω)，使得，ω ∈ S，且P(ω)不比 ω大出许多。所以，不那么正式地来说，我们可以认为NP有一个可被达到的脑力活动的集，当，我们能够判断ω ∈ S，且可以说服其他人我们做到了时。

布尔可满足性问题(Boolean satisfiability problem)，SAT，是第一个被证明的NP完全问题(Cook, 1971)，即，它是一个最难的NP问题。事实是，SAT是NP完全的，意味着，在NP中的所有问题都可被还原为SAT。多年来，研究者已经搭建了非常高效的SAT求解器，其可以快速地解决许多SAT的实例，即，找到一个可满足的指派，或者是证明没有这样的一个指派，甚至对于有着百万变量的实例来说。因此，SAT求解器被常用作通用问题求解器(general purpose problem solvers)。另一方面，对于一些已知的小实例类，当前的SAT求解器的是失败的。因此，P与NP问题的一部分涉及到，SAT的实际与理论复杂度(Nordström, 2015)。

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。