数学联邦政治世界观
超小超大

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),接着再看更方便。

相关小说

小心是我弟弟 连载中
小心是我弟弟
灵心白
请你看第一章
4.3万字8个月前
奇幻之都,奇幻之主 连载中
奇幻之都,奇幻之主
六夜浔语
从妄想中,出现了我的桃花源。那里……是我的家。作者自己的故事,部分根据真实内容改编。
26.1万字8个月前
情念与幻想 连载中
情念与幻想
缘落.^
0.1万字9个月前
我在话本市的日常 连载中
我在话本市的日常
汐司
话本市里那些搞笑、奇葩日常生活,即将播出,请观看。【文中部分话本人,都是有原型的,可在评论区留下你在这里的模样与契光者模样、性格】
5.6万字8个月前
我在梦境开外挂 连载中
我在梦境开外挂
秫禾羽青
【已签约】“晚上没事就睡觉,千万不要乱点奇怪的文章”被没用的系统绑定的少女如是说到在某一天她就手贱点下了那个奇怪的文章,然后就“被迫”加入了......
35.7万字8个月前
穿进ABO我自食其力 连载中
穿进ABO我自食其力
该用户已注销
abo文,有私设!!!特级杀手意外穿进了一个令他三观破裂的ABO世界,Omega要像女人一样结婚生子,而且还有发情期这么不科学的设定!不仅如......
8.3万字8个月前