SEP：可计算性与复杂性（三）

4.1 Significance of Complexity

下面那张图画出了我们已经讨论过的所有复杂性类和一些其他类。这张图来自于描述复杂性的工作(Immerman, 1999)，这表明了所有重要的复杂性类都有其描述性特征。Fagin通过提供了NP = SO∃的证明而开启了这个领域。即，一个性质属于NP，当且仅当，它在存在性二阶逻辑(existential second-order logic)中是可表达的(Fagin, 1974)。

Vardi与本词条的作者之后独立证明了P＝FO(LEP)：一个性质属于P，当且仅当，其在一阶逻辑加上一个最小不动点运算符(least fixed-point operator, LFP)后，是可表达的，这个最小不动点运算符形式化了通过归纳去定义新关系的能力。其中一个有趣的推论是 P＝NPiffSO＝FO(LFP)。这意味着，P是等于NP的，当且仅当，所有在二阶逻辑中是可表达的性质，在一阶逻辑中加上归纳定义时也是可表达的(有关，语言是否超过了，有限的有序输入结构，这个问题的更多细节，见(Immerman, 1999))。

co-re.complete Arithmetic Hierarchy FO(N) ── co-r.e. FO∀(N) r.e. FO∃(N)

r.e. complete Hali

Recursive

Primitive Recursive

EXPTIME

SO(LFP) SO[2ⁿᵒ⁽¹⁾)

QSAT PSPACE complete

PSPACE

FO[2ⁿᵒ⁽¹⁾] FO(PFP) SO(TC) SO[nᵒ⁽¹⁾]

co-NP complete PTIME Hierarchy SO

─── NP complete SAT

SAT

co-NP SO∀ NP SO∃

NP∩co-NP

FO[nᵒ⁽¹⁾] P complete P

FO(LFP) SO(Horn) Horn-SAT

FO[(log n)ᵒ⁽¹⁾] “truly NC

FO[log n] feasible” AC¹

FO(CFL) sAC¹

FO(TC) SO(Krom) 2SAT NL comp. NL

FO(DTC) 2COLOR L comp. L

FO(REGULAR) NC¹

FO(COUNT) ThC⁰

FO LOGTIME Hierarchy AC³

The World of Computability and Complexity

图中顶端的右边是递归可枚举问题，其包括了递归可枚举完全问题，例如停机问题。而在左边是共递归可枚举问题的集，包括共递归可枚举完全问题

──

Hαlt，即，永远不会在给定输出上停机的图灵机集。在2.3节的最后，我们提到了递归可枚举问题集，与共递归可枚举问题集的交集，是等于递归问题集的。原始递归问题集是递归问题的一个真子集。

让我们将目光移向这张图的底部，其有一个区域被用绿色虚线标记出了“真正可行(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://www.bjxsw.cc），接着再看更方便。