查看“︁多項式譜系”︁的源代码

{{no footnotes|time=2018-08-13T15:06:59+00:00}}
[[计算复杂度理论]]中，'''多项式谱系'''是一个复杂度系列。它从[[P_(复杂度)|P]]、[[NP_(复杂度)|NP]]和[[反NP]]复杂度类逐级产生至[[预言机]]。它类似于[[数理逻辑]]中[[算数阶层]]和[[分析阶层]]，只不过是由逐级放宽资源限制而产生的。

==定义==
多项式谱系有数个等价的定义。
{{ordered list|
1= 用预言机定义多项式谱系。首先定义

:<math>\Delta_0^\mathsf{P} := \Sigma_0^\mathsf{P} := \Pi_0^\mathsf{P} := \mathsf{P},</math>

其中[[P (复杂度)|P]]是能在[[多项式时间]]内解决的[[决定性问题]]。然后对所有<math>i \ge 0</math>定义

:<math>\Delta_{i+1}^\mathsf{P} := \mathsf{P}^{\Sigma_i^\mathsf{P}}</math>
:<math>\Sigma_{i+1}^\mathsf{P} := \mathsf{NP}^{\Sigma_i^\mathsf{P}}</math>
:<math>\Pi_{i+1}^\mathsf{P} := \mathsf{coNP}^{\Sigma_i^\mathsf{P}}</math>

其中<math>\mathsf{P}^{\rm A}</math>是在有<math>{\rm A}</math>类中某些[[完备_(复杂度)|完备问题]]的[[预言机]]辅助的情况下，能在多项式时间内由[[图灵机]]解决的[[决定性问题]]的集合。类别<math>\mathsf{NP}^{\rm A}</math>和<math>\mathsf{coNP}^{\rm A}</math>也有类似的定义。比如，<math>\Sigma_1^\mathsf{P} = \mathsf{NP}</math>、 <math>\Pi_1^\mathsf{P} = \mathsf{coNP} </math>和<math> \Delta_2^\mathsf{P} = \mathsf{P^{NP}} </math>是一些能在某些[[NP完全]]问题预言机的辅助下，在多项式时间内解决的问题的复杂度类。<ref>Completeness in the Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans</ref>

|2=用存在状态或者全称状态定义多项式谱系。令<math>L</math>为一个语言（或称为决定性问题，即<math>\{0,1\}^*</math>的某个子集），<math>p</math>为某多项式，定义

:<math> \exists^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \exists w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\}, </math>

其中<math>\langle x,w \rangle \in \{0,1\}^*</math>为某种将二进制字符串对<math>x</math>和<math>w</math>编码为一个二进制字符串的标准编码。<math>L</math>代表一个有序的字符串对的集合，其中第一个字符串{{mvar|x}}是<math>\exists^p L</math>的元素，而第二个字符串<math>w</math>是一个足够短的（长度不大于<math>p(|x|)</math>）见证<math>x</math>在<math>\exists^p L</math>内的字符串。换句话说，<math>x \in \exists^p L</math>当且仅当存在足够短的见证字符串<math>w</math>使得<math>\langle x,w \rangle \in L</math>。类似地，定义

:<math> \forall^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \forall w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\} </math>

注意到由[[德摩根定律]]得出<math>\left( \exists^p L \right)^{\rm c} = \forall^p L^{\rm c} </math> and <math> \left( \forall^p L \right)^{\rm c} = \exists^p L^{\rm c}</math>，其中<math>L^c</math>是<math>L</math>的补集。令<math>\mathcal{C}</math>为一个语言集。延伸这些运算使得它们能够应用于语言集上：

:<math>\exists^\mathsf{P} \mathcal{C} := \left\{\exists^p L \ | \ p \in \mathcal{P}, L \in \mathcal{C} \right\}</math>
:<math>\forall^\mathsf{P} \mathcal{C} := \left\{\forall^p L \ | \ p \in \mathcal{P}, L \in \mathcal{C} \right\}</math>

其中<math>\mathcal{P}</math>为所有多项式的集合。同样德摩根定律成立<math> \mathsf{co} \exists^\mathsf{P} \mathcal{C} = \forall^\mathsf{P} \mathsf{co} \mathcal{C} </math>以及<math> \mathsf{co} \forall^\mathsf{P} \mathcal{C} = \exists^\mathsf{P} \mathsf{co} \mathcal{C} </math>，其中<math>\mathsf{co}\mathcal{C} = \left\{ L^c | L \in \mathcal{C} \right\}</math>。

复杂度类NP和反NP可被定义为<math> \mathsf{NP} = \exists^\mathsf{P} \mathsf{P} </math>和<math> \mathsf{coNP} = \forall^\mathsf{P} \mathsf{P} </math>, 其中P是所有可行的（多项式时间内的）递归语言。则多项式谱系可被递归定义为

:<math> \Sigma_0^\mathsf{P} := \Pi_0^\mathsf{P} := \mathsf{P} </math>
:<math> \Sigma_{k+1}^\mathsf{P} := \exists^\mathsf{P} \Pi_k^\mathsf{P} </math>
:<math> \Pi_{k+1}^\mathsf{P} := \forall^\mathsf{P} \Sigma_k^\mathsf{P} </math>

注意<math> \mathsf{NP} = \Sigma_1^\mathsf{P} </math>, and <math> \mathsf{coNP} = \Pi_1^\mathsf{P} </math>。这个定义反映出多项式谱系和算数阶层之间的紧密关系。其中[[递归语言|R]]和[[递归可枚举语言|RE]]分别扮演了类似[[P_(复杂度)|P]]和[[NP_(复杂度)|NP]]的角色。算数阶层同样是用一系列的实数子集来定义的。

|3=用[[交替式图灵机]]的等价定义。定义<math>\Sigma_k^\mathsf{P}</math>（或<math>\Pi_k^\mathsf{P}</math>）为从存在状态（或全称状态）开始的<math>k</math>次交替式图灵机能够解决的问题的集合。

}}

==多项式谱系类别之间的关系==
[[Image:Polynomial time hierarchy.svg|250px|thumb|right|与多项式谱系等价的交换图表。箭头表示包含于。]]
由定义可推论出如下关系：
:<math> \Sigma_i^\mathsf{P}\subseteq \Delta_{i+1}^\mathsf{P} \subseteq \Sigma_{i+1}^\mathsf{P} </math>
:<math> \Pi_i^\mathsf{P} \subseteq \Delta_{i+1}^\mathsf{P} \subseteq \Pi_{i+1}^\mathsf{P} </math>
:<math> \Sigma_i^\mathsf{P} = \mathsf{co}\Pi_i^\mathsf{P} </math>
算术阶层和分析阶层中各层次包含关系都已确定为真包含，而多项式谱系中的这些包含关系是否为真包含仍未有定论，但人们普遍相信它们是真包含。如果任一<math>\Sigma_k^\mathsf{P}=\Sigma_{k+1}^\mathsf{P}</math>，或者<math>\Sigma_k^\mathsf{P}=\Pi_k^\mathsf{P}</math>，那么整个多项式层级将坍缩至<math>k</math>层：对任一<math>i>k</math>，都有<math>\Sigma_i^\mathsf{P}=\Sigma_k^\mathsf{P}</math>。特别的，如果<math>\mathsf{P}=\mathsf{NP}</math>，那么多项式谱系将完全坍缩。

所有多项式层级的类别的并集为复杂度类[[PH_(复杂度)|PH]]。

==性质==
{{unsolved|计算机科学|{{tmath|1= \mathsf{PH} \overset{?}{=} \mathsf{PSPACE} }}}}
多项式谱系与[[指数谱系]]和[[算术阶层]]类似，但复杂度更小。

已经确定PH包含于[[PSPACE]]，但不确定两者是否相等。这个问题有一个很有用的变体：PH = PSPACE当且仅当[[传递闭包#与复杂性的关系|二阶逻辑复杂度类]]不能通过传递闭包运算扩展计算能力。

如果多项式谱系中有任何[[完备_(复杂度)|完备问题]]，那么它仅有有限个不同的层次。我们知道存在PSPACE完备问题，所以如果PH = PSPACE，PH必然坍缩，因为对任一PSPACE完备问题必然存在整数<math>k</math>使得这个问题是<math>\Sigma_k^\mathsf{P}</math>完备的。

每个多项式谱系中的复杂度类都包含<math>\leq_m^p</math>完备问题（指多项式次多对一规约的完备问题）。而且每个多项式谱系中的复杂度类都对<math>\leq_m^p</math>规约封闭，也就是说对于一个多项式谱系中的复杂度类<math>\mathcal{C}</math>和一个语言<math>\mathcal{L}\in \mathcal{C}</math>，如果<math>A\leq_m^p\mathcal{L}</math>，那么<math>A\in \mathcal{C}</math>。这两个事实表明如果<math>K_i</math>是<math>\Sigma_i^\mathsf{P}</math>的完备问题，那么<math>\Sigma_{i+1}^\mathsf{P}=\mathsf{NP}^{K_i}</math>，并且<math>\Pi_{i+1}^\mathsf{P}=\mathsf{coNP}^{K_i}</math>。比如说<math>\Sigma_2^\mathsf{P}=\mathsf{NP}^\mathsf{SAT}</math>。换句话说，如果一个语言是由某个<math>\mathcal{C}</math>预言机定义的，那么我们就可以假设它是基于<math>\mathcal{C}</math>中的某个完备问题定义的。完备问题这里就相当于对应复杂度类的一个“代表”。

{{Link-en|Sipser–Lautemann定理|Sipser–Lautemann_theorem}}说明[[BPP_(复杂度)|BPP]]包含于多项式谱系中的第二层。

{{Link-en|Kannan定理|Karp–Lipton_theorem#Application_to_circuit_lower_bounds_–_Kannan's_theorem}}说明对于任意<math>k</math>，<math>\Sigma_2</math>都不包含于<math>\mathsf{SIZE}(n^k)</math>。

[[户田定理]]说明PH包含于<math>\mathsf{P}^\mathsf{\#P}</math>。

==多项式谱系中的问题==
* 电路最小化是<math>\Sigma_2^\mathsf{P}</math>中的一个自然问题。给定数字<math>k</math>和计算[[布尔函数]]<math>f</math>的电路<math>A</math>，判定是否存在能够计算<math>f</math>并且至多<math>k</math>个门的电路。令<math>\mathcal{C}</math>为所有布尔电路的集合。令<math>G(f)</math>为计算<math>f</math>门数的函数。则语言

:<math>L = \{\langle A,k,B,x\rangle \in \mathcal{C}\times \mathbb{N}\times \mathcal{C}\times \{0, 1\}^* | G(B)\leq k\wedge A = B\} </math>

可在多项式时间内确定。语言

:<math> CM = \{\langle A, k\rangle \in \mathcal{C}\times \mathbb{N} | \exists B\in \mathcal{C}\wedge G(B)\leq k\wedge A = B\} </math>

为最小化电路语言。<math>CM\in \Sigma_2^\mathsf{P}(=\exists^\mathsf{P}\forall^\mathsf{P}\mathsf{P})</math>因为<math>L</math>在多项式时间内可判定，并且给定<math>\langle A,k\rangle</math>，<math>\langle A,k\rangle\in CM</math>当且仅当''存在''电路<math>B</math>使得对于''所有''输入<math>x</math>，<math>\langle A, k, B, x\rangle\in L</math>。

* 一个<math>\Sigma_k^\mathsf{P}</math>完备问题是有<math>k</math>量词交替的布尔公式的可满足性（缩写为'''QBF<sub>k</sub>'''或者'''QSAT<sub>k</sub>'''）。这是<math>\Sigma_k^\mathsf{P}</math>版本的布尔可满足性问题。在这个问题中布尔公式<math>f</math>的变量被分成了<math>k</math>个集合<math>X_1, X_2,\dots X_k</math>。我们需要确定
:<math>\exists X_1\forall X_2\exists X_3\dots f</math>
是否为真。也就是说存在对<math>X_1</math>的赋值，使得对所有的<math>X_2</math>, 存在对<math>X_3</math>的赋值，……，使得<math>f</math>为真。从[[全称量词]]开始交替到[[存在量词]]再到全称量词的变体则是<math>\Pi_k^\mathsf{P}</math>完备的。

* 这份[http://ovid.cs.depaul.edu/documents/phcom.pdf 概要]{{Wayback|url=http://ovid.cs.depaul.edu/documents/phcom.pdf |date=20170712203350 }}包含一份M.R.加里/D.S.约翰逊样式的二阶或更高阶的完备问题清单。

==另见==
* [[EXPTIME]]
* [[指数谱系]]
* [[算术阶层]]

==参考文献==
# [[Albert R. Meyer|A. R. Meyer]] and [[Larry Stockmeyer|L. J. Stockmeyer]].  The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space.  ''In Proceedings of the 13th IEEE [[Symposium on Switching and Automata Theory]]'', pp.&nbsp;125&ndash;129, 1972.  The paper that introduced the polynomial hierarchy.
# [[Larry Stockmeyer|L. J. Stockmeyer]]. [[:doi:10.1016/0304-3975(76)90061-X|The polynomial-time hierarchy]]. ''Theoretical Computer Science'', vol.3, pp.&nbsp;1&ndash;22, 1976.
# [[Christos Papadimitriou|C. Papadimitriou]]. Computational Complexity. Addison-Wesley, 1994. Chapter 17. ''Polynomial hierarchy'', pp.&nbsp;409&ndash;438.
# {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = 0-7167-1045-5}} Section 7.2: The Polynomial Hierarchy, pp.&nbsp;161–167.

==引用==
<references/>

{{复杂度类}}

[[Category:数学术语]]
[[Category:計算複雜性理論]]