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

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))。

plete 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节的最后，我们提到了递归可枚举问题集，与共递归可枚举问题集的交集，是等于递归问题集的。原始递归问题集是递归问题的一个真子集。

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