多項式階層 (たこうしきかいそう、英 : Polynomial hierarchy )は、計算量理論 における計算量の階層であり、神託機械 を使って P 、NP 、co-NP を一般化させて定義されるものである。
多項式階層をなすクラス群の定義はいくつか存在する。
多項式階層は神託機械を使って次のように定義する。
Δ
0
P
:=
Σ
0
P
:=
Π
0
P
:=
P
,
{\displaystyle \Delta _{0}^{\rm {P}}:=\Sigma _{0}^{\rm {P}}:=\Pi _{0}^{\rm {P}}:={\mbox{P}},}
ここで、P は多項式時間 内で解ける決定問題 の集合である。i ≥ 0 については、次のように定義する。
ここで、AB はクラス A のチューリングマシン にクラス B の何らかの問題を解く神託 を付加して強化したもので解ける決定問題 の集合である。例えば、
Σ
1
P
=
N
P
,
Π
1
P
=
c
o
N
P
{\displaystyle \Sigma _{1}^{\rm {P}}={\rm {NP}},\Pi _{1}^{\rm {P}}={\rm {coNP}}}
であり、
Δ
2
P
=
P
N
P
{\displaystyle \Delta _{2}^{\rm {P}}={\rm {P^{NP}}}}
は NP に属する何らかの問題を解く神託を備えることで多項式時間で解ける問題のクラスである。
多項式階層の存在/全称的定義のため、
L
{\displaystyle L}
を形式言語 (すなわち、一種の決定問題 であり、{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\}^{*}}
は2進文字列 x と w を1つの2進文字列にする何らかの標準的符号化である。L は文字列の順序対の集合を表しており、第一の文字列 x は
∃
p
L
{\displaystyle \exists ^{p}L}
の元で、第二の文字列 w は x が
∃
p
L
{\displaystyle \exists ^{p}L}
の元であることを示す短い (
|
w
|
≤
p
(
|
x
|
)
{\displaystyle |w|\leq p(|x|)}
) 証拠である。言い換えれば、
x
∈
∃
p
L
{\displaystyle x\in \exists ^{p}L}
は、
⟨
x
,
w
⟩
∈
L
{\displaystyle \langle x,w\rangle \in L}
であるような短い証拠 w が存在することと同値である。同様に次のように定義する。
∀
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}}}
かつ
(
∀
p
L
)
c
=
∃
p
L
c
{\displaystyle \left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}}
であり、ここで L c は L の補集合である。ここで
C
{\displaystyle {\mathcal {C}}}
を言語のクラスとする。次のように定義することで、これら作用素が言語のクラス群全体に作用するよう拡張する。
∃
P
C
:=
{
∃
p
L
|
p
is a polynomial and
L
∈
C
}
{\displaystyle \exists ^{\rm {P}}{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p{\mbox{ is a polynomial and }}L\in {\mathcal {C}}\right\}}
∀
P
C
:=
{
∀
p
L
|
p
is a polynomial and
L
∈
C
}
{\displaystyle \forall ^{\rm {P}}{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\mbox{ is a polynomial and }}L\in {\mathcal {C}}\right\}}
再びドモルガンの定理により、
c
o
∃
P
C
=
∀
P
c
o
C
{\displaystyle {\rm {co}}\exists ^{\rm {P}}{\mathcal {C}}=\forall ^{\rm {P}}{\rm {co}}{\mathcal {C}}}
かつ
c
o
∀
P
C
=
∃
P
c
o
C
{\displaystyle {\rm {co}}\forall ^{\rm {P}}{\mathcal {C}}=\exists ^{\rm {P}}{\rm {co}}{\mathcal {C}}}
であり、ここで
c
o
C
=
{
L
c
|
L
∈
C
}
{\displaystyle {\rm {co}}{\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}}
である。クラス NP と co-NP は
N
P
=
∃
P
P
{\displaystyle {\rm {NP}}=\exists ^{\rm {P}}{\rm {P}}}
と
c
o
N
P
=
∀
P
P
{\displaystyle {\rm {coNP}}=\forall ^{\rm {P}}{\rm {P}}}
と定義され、ここで P は(多項式時間で)適切に決定可能な言語群の全体のクラスである。多項式階層は次のように再帰的に定義できる。
Σ
0
P
:=
Π
0
P
:=
P
{\displaystyle \Sigma _{0}^{\rm {P}}:=\Pi _{0}^{\rm {P}}:={\rm {P}}}
Σ
k
+
1
P
:=
∃
P
Π
k
P
{\displaystyle \Sigma _{k+1}^{\rm {P}}:=\exists ^{\rm {P}}\Pi _{k}^{\rm {P}}}
Π
k
+
1
P
:=
∀
P
Σ
k
P
{\displaystyle \Pi _{k+1}^{\rm {P}}:=\forall ^{\rm {P}}\Sigma _{k}^{\rm {P}}}
なお、
N
P
=
Σ
1
P
{\displaystyle {\rm {NP}}=\Sigma _{1}^{\rm {P}}}
であり、かつ
c
o
N
P
=
Π
1
P
{\displaystyle {\rm {coNP}}=\Pi _{1}^{\rm {P}}}
である。この定義は多項式階層と算術的階層 の密接な関連を反映しており、後者で DEC と CE が果たした役割をそれぞれ P と NP が果たしている。同様の方法で、実数の部分集合の階層として解析的階層 が定義される。
交替性チューリング機械 を使った等価な定義として、
Σ
k
P
{\displaystyle \Sigma _{k}^{\rm {P}}}
(あるいは
Π
k
P
{\displaystyle \Pi _{k}^{\rm {P}}}
)は存在的状態(あるいは全称的状態)から開始する交替性チューリング機械で
k
{\displaystyle k}
回の交替を行うことで多項式時間で解ける決定問題の集合と定義される。
多項式階層内のクラス間の関係
編集
多項式階層内の問題
編集
Σ
2
P
{\displaystyle \Sigma _{2}^{P}}
に属する問題の具体例として「回路最小化」問題がある。ある数 k とブール関数 f を計算する回路 A があるとき、同じ関数 f を最大 k 個の論理ゲートで計算できる回路が存在するかを問う決定問題である。
C
{\displaystyle {\mathcal {C}}}
を全ての論理回路の集合とする。この場合の言語 L は次のように定義される。
L
=
{
⟨
A
,
k
,
B
,
x
⟩
∈
C
×
N
×
C
×
{
0
,
1
}
∗
|
B
has at most
k
gates, and
A
(
x
)
=
B
(
x
)
}
{\displaystyle L=\left\{\langle A,k,B,x\rangle \in {\mathcal {C}}\times \mathbb {N} \times {\mathcal {C}}\times \{0,1\}^{*}\left|B{\mbox{ has at most }}k{\mbox{ gates, and }}A(x)=B(x)\right.\right\}}
これは多項式時間で決定可能である。次の言語 CM が回路最小化問題を表す言語である。
C
M
=
{
⟨
A
,
k
⟩
∈
C
×
N
|
there exists a circuit
B
with at most
k
gates
such that
A
and
B
compute the same function
}
{\displaystyle CM=\left\{\langle A,k\rangle \in {\mathcal {C}}\times \mathbb {N} \left|{\begin{matrix}{\mbox{there exists a circuit }}B{\mbox{ with at most }}k{\mbox{ gates }}\\{\mbox{ such that }}A{\mbox{ and }}B{\mbox{ compute the same function}}\end{matrix}}\right.\right\}}
L
{\displaystyle L}
が多項式時間で決定可能であり、かつ与えられた
⟨
A
,
k
⟩
{\displaystyle \langle A,k\rangle }
について
⟨
A
,
k
⟩
∈
C
M
{\displaystyle \langle A,k\rangle \in CM}
であることと全ての入力
x
{\displaystyle x}
について
⟨
A
,
k
,
B
,
x
⟩
∈
L
{\displaystyle \langle A,k,B,x\rangle \in L}
となる回路
B
{\displaystyle B}
が存在することは同値であることから、
C
M
∈
Σ
2
P
(
=
∃
P
∀
P
P
)
{\displaystyle CM\in \Sigma _{2}^{P}(=\exists ^{\rm {P}}\forall ^{\rm {P}}{\rm {P}})}
が成り立つ。
Σ
k
P
{\displaystyle \Sigma _{k}^{\rm {P}}}
の完全問題として k 回の量化子交替のある「限量記号付きブール式問題」(QBFk または QSATk と略記される)がある。これは充足可能性問題 を
Σ
k
P
{\displaystyle \Sigma _{k}^{\rm {P}}}
向けにしたものである。この問題では、与えられるブール論理式 f の変数は k 個の集合 X1 , ..., Xk に分けられる。ここで次が真かどうかを決定しなくてはならない。
∃
X
1
∀
X
2
∃
X
3
…
f
{\displaystyle \exists X_{1}\forall X_{2}\exists X_{3}\ldots f}
すなわち、X1 に f を満足する値の組合せがあり、かつ X2 の値の全ての組合せが f を満足し、かつ X3 に f を満足する値の組合せがあり、… という組合せが存在するかどうか、という問題である。この順序の問題は
Σ
k
P
{\displaystyle \Sigma _{k}^{\rm {P}}}
について完全である。全称記号が最初にあって、次が存在記号という順序になっている問題は
Π
k
P
{\displaystyle \Pi _{k}^{\rm {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. 多項式階層を提唱した論文。
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 (1979年). Computers and Intractability: A Guide to the Theory of NP-Completeness . W.H. Freeman. ISBN 0-7167-1045-5 Section 7.2: The Polynomial Hierarchy, pp.161–167.