計算複雜度理論 中,多項式譜系 是一個複雜度系列。它從P 、NP 和反NP 複雜度類逐級產生至預言機 。它類似於數理邏輯 中算數階層 和分析階層 ,只不過是由逐級放寬資源限制而產生的。
定義
多項式譜系有數個等價的定義。
用預言機定義多項式譜系。首先定義
Δ
0
P
:=
Σ
0
P
:=
Π
0
P
:=
P
,
{\displaystyle \Delta _{0}^{\mathsf {P}}:=\Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}},}
其中P 是能在多項式時間 內解決的決定性問題 。然後對所有
i
≥
0
{\displaystyle i\geq 0}
定義
Δ
i
+
1
P
:=
P
Σ
i
P
{\displaystyle \Delta _{i+1}^{\mathsf {P}}:={\mathsf {P}}^{\Sigma _{i}^{\mathsf {P}}}}
Σ
i
+
1
P
:=
N
P
Σ
i
P
{\displaystyle \Sigma _{i+1}^{\mathsf {P}}:={\mathsf {NP}}^{\Sigma _{i}^{\mathsf {P}}}}
Π
i
+
1
P
:=
c
o
N
P
Π
i
P
{\displaystyle \Pi _{i+1}^{\mathsf {P}}:={\mathsf {coNP}}^{\Pi _{i}^{\mathsf {P}}}}
其中
P
A
{\displaystyle {\mathsf {P}}^{\rm {A}}}
是在有
A
{\displaystyle {\rm {A}}}
類中某些完備問題 的預言機 輔助的情況下,能在多項式時間內由圖靈機 解決的決定性問題 的集合。類別
N
P
A
{\displaystyle {\mathsf {NP}}^{\rm {A}}}
和
c
o
N
P
A
{\displaystyle {\mathsf {coNP}}^{\rm {A}}}
也有類似的定義。比如,
Σ
1
P
=
N
P
{\displaystyle \Sigma _{1}^{\mathsf {P}}={\mathsf {NP}}}
、
Π
1
P
=
c
o
N
P
{\displaystyle \Pi _{1}^{\mathsf {P}}={\mathsf {coNP}}}
和
Δ
2
P
=
P
N
P
{\displaystyle \Delta _{2}^{\mathsf {P}}={\mathsf {P^{NP}}}}
是一些能在某些NP完全 問題預言機的輔助下,在多項式時間內解決的問題的複雜度類。[1] 用存在狀態或者全稱狀態定義多項式譜系。令
L
{\displaystyle L}
為一個語言(或稱為決定性問題,即
{
0
,
1
}
∗
{\displaystyle \{0,1\}^{*}}
的某個子集),
p
{\displaystyle p}
為某多項式,定義
∃
p
L
:=
{
x
∈
{
0
,
1
}
∗
|
(
∃
w
∈
{
0
,
1
}
≤
p
(
|
x
|
)
)
⟨
x
,
w
⟩
∈
L
}
,
{\displaystyle \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\},}
其中
⟨
x
,
w
⟩
∈
{
0
,
1
}
∗
{\displaystyle \langle x,w\rangle \in \{0,1\}^{*}}
為某種將二進制字符串對
x
{\displaystyle x}
和
w
{\displaystyle w}
編碼為一個二進制字符串的標準編碼。
L
{\displaystyle L}
代表一個有序的字符串對的集合,其中第一個字符串x 是
∃
p
L
{\displaystyle \exists ^{p}L}
的元素,而第二個字符串
w
{\displaystyle w}
是一個足夠短的(長度不大於
p
(
|
x
|
)
{\displaystyle p(|x|)}
)見證
x
{\displaystyle x}
在
∃
p
L
{\displaystyle \exists ^{p}L}
內的字符串。換句話說,
x
∈
∃
p
L
{\displaystyle x\in \exists ^{p}L}
當且僅當存在足夠短的見證字符串
w
{\displaystyle w}
使得
⟨
x
,
w
⟩
∈
L
{\displaystyle \langle x,w\rangle \in L}
。類似地,定義
∀
p
L
:=
{
x
∈
{
0
,
1
}
∗
|
(
∀
w
∈
{
0
,
1
}
≤
p
(
|
x
|
)
)
⟨
x
,
w
⟩
∈
L
}
{\displaystyle \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\}}
注意到由德摩根定律 得出
(
∃
p
L
)
c
=
∀
p
L
c
{\displaystyle \left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}}
and
(
∀
p
L
)
c
=
∃
p
L
c
{\displaystyle \left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}}
,其中
L
c
{\displaystyle L^{c}}
是
L
{\displaystyle L}
的補集。令
C
{\displaystyle {\mathcal {C}}}
為一個語言集。延伸這些運算使得它們能夠應用於語言集上:
∃
P
C
:=
{
∃
p
L
|
p
∈
P
,
L
∈
C
}
{\displaystyle \exists ^{\mathsf {P}}{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p\in {\mathcal {P}},L\in {\mathcal {C}}\right\}}
∀
P
C
:=
{
∀
p
L
|
p
∈
P
,
L
∈
C
}
{\displaystyle \forall ^{\mathsf {P}}{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p\in {\mathcal {P}},L\in {\mathcal {C}}\right\}}
其中
P
{\displaystyle {\mathcal {P}}}
為所有多項式的集合。同樣德摩根定律成立
c
o
∃
P
C
=
∀
P
c
o
C
{\displaystyle {\mathsf {co}}\exists ^{\mathsf {P}}{\mathcal {C}}=\forall ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}}
以及
c
o
∀
P
C
=
∃
P
c
o
C
{\displaystyle {\mathsf {co}}\forall ^{\mathsf {P}}{\mathcal {C}}=\exists ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}}
,其中
c
o
C
=
{
L
c
|
L
∈
C
}
{\displaystyle {\mathsf {co}}{\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}}
。
複雜度類NP和反NP可被定義為
N
P
=
∃
P
P
{\displaystyle {\mathsf {NP}}=\exists ^{\mathsf {P}}{\mathsf {P}}}
和
c
o
N
P
=
∀
P
P
{\displaystyle {\mathsf {coNP}}=\forall ^{\mathsf {P}}{\mathsf {P}}}
, 其中P是所有可行的(多項式時間內的)遞歸語言。則多項式譜系可被遞歸定義為
Σ
0
P
:=
Π
0
P
:=
P
{\displaystyle \Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}}}
Σ
k
+
1
P
:=
∃
P
Π
k
P
{\displaystyle \Sigma _{k+1}^{\mathsf {P}}:=\exists ^{\mathsf {P}}\Pi _{k}^{\mathsf {P}}}
Π
k
+
1
P
:=
∀
P
Σ
k
P
{\displaystyle \Pi _{k+1}^{\mathsf {P}}:=\forall ^{\mathsf {P}}\Sigma _{k}^{\mathsf {P}}}
注意
N
P
=
Σ
1
P
{\displaystyle {\mathsf {NP}}=\Sigma _{1}^{\mathsf {P}}}
, and
c
o
N
P
=
Π
1
P
{\displaystyle {\mathsf {coNP}}=\Pi _{1}^{\mathsf {P}}}
。這個定義反映出多項式譜系和算數階層之間的緊密關係。其中R 和RE 分別扮演了類似P 和NP 的角色。算數階層同樣是用一系列的實數子集來定義的。 用交替式圖靈機 的等價定義。定義
Σ
k
P
{\displaystyle \Sigma _{k}^{\mathsf {P}}}
(或
Π
k
P
{\displaystyle \Pi _{k}^{\mathsf {P}}}
)為從存在狀態(或全稱狀態)開始的
k
{\displaystyle k}
次交替式圖靈機能夠解決的問題的集合。
多項式譜系類別之間的關係
與多項式譜系等價的交換圖表。箭頭表示包含於。
由定義可推論出如下關係:
Σ
i
P
⊆
Δ
i
+
1
P
⊆
Σ
i
+
1
P
{\displaystyle \Sigma _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Sigma _{i+1}^{\mathsf {P}}}
Π
i
P
⊆
Δ
i
+
1
P
⊆
Π
i
+
1
P
{\displaystyle \Pi _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Pi _{i+1}^{\mathsf {P}}}
Σ
i
P
=
c
o
Π
i
P
{\displaystyle \Sigma _{i}^{\mathsf {P}}={\mathsf {co}}\Pi _{i}^{\mathsf {P}}}
算術階層和分析階層中各層次包含關係都已確定為真包含,而多項式譜系中的這些包含關係是否為真包含仍未有定論,但人們普遍相信它們是真包含。如果任一
Σ
k
P
=
Σ
k
+
1
P
{\displaystyle \Sigma _{k}^{\mathsf {P}}=\Sigma _{k+1}^{\mathsf {P}}}
,或者
Σ
k
P
=
Π
k
P
{\displaystyle \Sigma _{k}^{\mathsf {P}}=\Pi _{k}^{\mathsf {P}}}
,那麼整個多項式層級將坍縮至
k
{\displaystyle k}
層:對任一
i
>
k
{\displaystyle i>k}
,都有
Σ
i
P
=
Σ
k
P
{\displaystyle \Sigma _{i}^{\mathsf {P}}=\Sigma _{k}^{\mathsf {P}}}
。特別的,如果
P
=
N
P
{\displaystyle {\mathsf {P}}={\mathsf {NP}}}
,那麼多項式譜系將完全坍縮。
所有多項式層級的類別的併集為複雜度類PH 。
性質
未解決的計算機科學問題 :
P
H
=
?
P
S
P
A
C
E
{\displaystyle {\mathsf {PH}}{\overset {?}{=}}{\mathsf {PSPACE}}}
多項式譜系與指數譜系 和算術階層 類似,但複雜度更小。
已經確定PH包含於PSPACE ,但不確定兩者是否相等。這個問題有一個很有用的變體:PH = PSPACE當且僅當二階邏輯複雜度類 不能通過傳遞閉包運算擴展計算能力。
如果多項式譜系中有任何完備問題 ,那麼它僅有有限個不同的層次。我們知道存在PSPACE完備問題,所以如果PH = PSPACE,PH必然坍縮,因為對任一PSPACE完備問題必然存在整數
k
{\displaystyle k}
使得這個問題是
Σ
k
P
{\displaystyle \Sigma _{k}^{\mathsf {P}}}
完備的。
每個多項式譜系中的複雜度類都包含
≤
m
p
{\displaystyle \leq _{m}^{p}}
完備問題(指多項式次多對一規約的完備問題)。而且每個多項式譜系中的複雜度類都對
≤
m
p
{\displaystyle \leq _{m}^{p}}
規約封閉,也就是說對於一個多項式譜系中的複雜度類
C
{\displaystyle {\mathcal {C}}}
和一個語言
L
∈
C
{\displaystyle {\mathcal {L}}\in {\mathcal {C}}}
,如果
A
≤
m
p
L
{\displaystyle A\leq _{m}^{p}{\mathcal {L}}}
,那麼
A
∈
C
{\displaystyle A\in {\mathcal {C}}}
。這兩個事實表明如果
K
i
{\displaystyle K_{i}}
是
Σ
i
P
{\displaystyle \Sigma _{i}^{\mathsf {P}}}
的完備問題,那麼
Σ
i
+
1
P
=
N
P
K
i
{\displaystyle \Sigma _{i+1}^{\mathsf {P}}={\mathsf {NP}}^{K_{i}}}
,並且
Π
i
+
1
P
=
c
o
N
P
K
i
{\displaystyle \Pi _{i+1}^{\mathsf {P}}={\mathsf {coNP}}^{K_{i}}}
。比如說
Σ
2
P
=
N
P
S
A
T
{\displaystyle \Sigma _{2}^{\mathsf {P}}={\mathsf {NP}}^{\mathsf {SAT}}}
。換句話說,如果一個語言是由某個
C
{\displaystyle {\mathcal {C}}}
預言機定義的,那麼我們就可以假設它是基於
C
{\displaystyle {\mathcal {C}}}
中的某個完備問題定義的。完備問題這裡就相當於對應複雜度類的一個「代表」。
Sipser–Lautemann定理 說明BPP 包含於多項式譜系中的第二層。
Kannan定理 說明對於任意
k
{\displaystyle k}
,
Σ
2
{\displaystyle \Sigma _{2}}
都不包含於
S
I
Z
E
(
n
k
)
{\displaystyle {\mathsf {SIZE}}(n^{k})}
。
戶田定理 說明PH包含於
P
#
P
{\displaystyle {\mathsf {P}}^{\mathsf {\#P}}}
。
多項式譜系中的問題
電路最小化是
Σ
2
P
{\displaystyle \Sigma _{2}^{\mathsf {P}}}
中的一個自然問題。給定數字
k
{\displaystyle k}
和計算布爾函數
f
{\displaystyle f}
的電路
A
{\displaystyle A}
,判定是否存在能夠計算
f
{\displaystyle f}
並且至多
k
{\displaystyle k}
個門的電路。令
C
{\displaystyle {\mathcal {C}}}
為所有布爾電路的集合。令
G
(
f
)
{\displaystyle G(f)}
為計算
f
{\displaystyle f}
門數的函數。則語言
L
=
{
⟨
A
,
k
,
B
,
x
⟩
∈
C
×
N
×
C
×
{
0
,
1
}
∗
|
G
(
B
)
≤
k
∧
A
=
B
}
{\displaystyle 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\}}
可在多項式時間內確定。語言
C
M
=
{
⟨
A
,
k
⟩
∈
C
×
N
|
∃
B
∈
C
∧
G
(
B
)
≤
k
∧
A
=
B
}
{\displaystyle CM=\{\langle A,k\rangle \in {\mathcal {C}}\times \mathbb {N} |\exists B\in {\mathcal {C}}\wedge G(B)\leq k\wedge A=B\}}
為最小化電路語言。
C
M
∈
Σ
2
P
(
=
∃
P
∀
P
P
)
{\displaystyle CM\in \Sigma _{2}^{\mathsf {P}}(=\exists ^{\mathsf {P}}\forall ^{\mathsf {P}}{\mathsf {P}})}
因為
L
{\displaystyle L}
在多項式時間內可判定,並且給定
⟨
A
,
k
⟩
{\displaystyle \langle A,k\rangle }
,
⟨
A
,
k
⟩
∈
C
M
{\displaystyle \langle A,k\rangle \in CM}
當且僅當存在 電路
B
{\displaystyle B}
使得對於所有 輸入
x
{\displaystyle x}
,
⟨
A
,
k
,
B
,
x
⟩
∈
L
{\displaystyle \langle A,k,B,x\rangle \in L}
。
一個
Σ
k
P
{\displaystyle \Sigma _{k}^{\mathsf {P}}}
完備問題是有
k
{\displaystyle k}
量詞交替的布爾公式的可滿足性(縮寫為QBFk 或者QSATk )。這是
Σ
k
P
{\displaystyle \Sigma _{k}^{\mathsf {P}}}
版本的布爾可滿足性問題。在這個問題中布爾公式
f
{\displaystyle f}
的變量被分成了
k
{\displaystyle k}
個集合
X
1
,
X
2
,
…
X
k
{\displaystyle X_{1},X_{2},\dots X_{k}}
。我們需要確定
∃
X
1
∀
X
2
∃
X
3
…
f
{\displaystyle \exists X_{1}\forall X_{2}\exists X_{3}\dots f}
是否為真。也就是說存在對
X
1
{\displaystyle X_{1}}
的賦值,使得對所有的
X
2
{\displaystyle X_{2}}
, 存在對
X
3
{\displaystyle X_{3}}
的賦值,……,使得
f
{\displaystyle f}
為真。從全稱量詞 開始交替到存在量詞 再到全稱量詞的變體則是
Π
k
P
{\displaystyle \Pi _{k}^{\mathsf {P}}}
完備的。
另見
參考文獻
A. R. Meyer and 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. 125–129, 1972. The paper that introduced the polynomial hierarchy.
L. J. Stockmeyer . The polynomial-time hierarchy . Theoretical Computer Science , vol.3, pp. 1–22, 1976.
C. Papadimitriou . Computational Complexity. Addison-Wesley, 1994. Chapter 17. Polynomial hierarchy , pp. 409–438.
Michael R. Garey and David S. Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness . W.H. Freeman. 1979. ISBN 0-7167-1045-5 . Section 7.2: The Polynomial Hierarchy, pp. 161–167.
引用
Completeness in the Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans