定义
多项式谱系有数个等价的定义。
- 用预言机定义多项式谱系。首先定义
-
其中P是能在多项式时间内解决的决定性问题。然后对所有 定义
-
-
-
其中 是在有 类中某些完备问题的预言机辅助的情况下,能在多项式时间内由图灵机解决的决定性问题的集合。类别 和 也有类似的定义。比如, 、 和 是一些能在某些NP完全问题预言机的辅助下,在多项式时间内解决的问题的复杂度类。[1] - 用存在状态或者全称状态定义多项式谱系。令 为一个语言(或称为决定性问题,即 的某个子集), 为某多项式,定义
-
其中 为某种将二进制字符串对 和 编码为一个二进制字符串的标准编码。 代表一个有序的字符串对的集合,其中第一个字符串x是 的元素,而第二个字符串 是一个足够短的(长度不大于 )见证 在 内的字符串。换句话说, 当且仅当存在足够短的见证字符串 使得 。类似地,定义
-
注意到由德摩根定律得出 and ,其中 是 的补集。令 为一个语言集。延伸这些运算使得它们能够应用于语言集上:
-
-
其中 为所有多项式的集合。同样德摩根定律成立 以及 ,其中 。
复杂度类NP和反NP可被定义为 和 , 其中P是所有可行的(多项式时间内的)递归语言。则多项式谱系可被递归定义为
-
-
-
注意 , and 。这个定义反映出多项式谱系和算数阶层之间的紧密关系。其中R和RE分别扮演了类似P和NP的角色。算数阶层同样是用一系列的实数子集来定义的。 - 用交替式图灵机的等价定义。定义 (或 )为从存在状态(或全称状态)开始的 次交替式图灵机能够解决的问题的集合。
多项式谱系类别之间的关系
性质
多项式谱系中的问题
- 电路最小化是 中的一个自然问题。给定数字 和计算布尔函数 的电路 ,判定是否存在能够计算 并且至多 个门的电路。令 为所有布尔电路的集合。令 为计算 门数的函数。则语言
-
可在多项式时间内确定。语言
-
为最小化电路语言。 因为 在多项式时间内可判定,并且给定 , 当且仅当存在电路 使得对于所有输入 , 。
- 一个 完备问题是有 量词交替的布尔公式的可满足性(缩写为QBFk或者QSATk)。这是 版本的布尔可满足性问题。在这个问题中布尔公式 的变量被分成了 个集合 。我们需要确定
-
是否为真。也就是说存在对 的赋值,使得对所有的 , 存在对 的赋值,……,使得 为真。从全称量词开始交替到存在量词再到全称量词的变体则是 完备的。
另见
参考文献
引用
- ^ Completeness in the Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans