多項式階層
Polynomial hierarchy
複数の方法で定義される
定義
言語$ Lが$ \mathbf \Sigma^p_nであるとは多項式長の$ \Sigma_n論理式で表現できることである。すなわち多項式$ qが存在して以下を満たすことである
$ x \in L \iff (\exists u_1 \in 2^{q(|x|)})(\forall u_2 \in 2^{q(|x|)}) ... (\mathsf{Q} u_n \in 2^{q(|x|)})[M(x, u_1, u_2, ... u_n) = 1]
言語$ Lが$ \mathbf \Pi^p_nであるとは多項式長の$ \Pi_n論理式で表現できることである。すなわち多項式$ qが存在して以下を満たすことである
$ x \in L \iff (\forall u_1 \in 2^{q(|x|)})(\exists u_2 \in 2^{q(|x|)}) ... (\mathsf{Q} u_n \in 2^{q(|x|)})[M(x, u_1, u_2, ... u_n) = 1]
$ \mathbf{PH} := \bigcup_n \mathbf{\Sigma}^p_n
性質
$ \mathbf{co\Sigma}^p_n = \mathbf{\Pi}^p_n, $ \mathbf{co\Pi}^p_n = \mathbf{\Sigma}^p_n
$ \mathbf{\Sigma}^p_0 = \mathbf{\Pi}^p_0 = \mathbf{P}, $ \mathbf{\Sigma}^p_1 = \mathbf{NP}, $ \mathbf{\Pi}^p_1 = \mathbf{coNP}
$ \mathbf{\Sigma}^p_n \cup \mathbf{\Pi}^p_n \subseteq \mathbf{\Sigma}^p_{n+1} \cap \mathbf{\Pi}^p_{n+1}
$ \mathbf{PH} = \bigcup_n \mathbf{\Pi}^p_n
$ \mathbf{\Sigma}^p_n \subseteq \mathbf{\Pi}^p_{n+1}, $ \mathbf{\Pi}^p_n \subseteq \mathbf{\Sigma}^p_{n+1}だから
$ \mathbf{\Sigma}^p_i = \mathbf{\Pi}^p_i , $ i \ge 1ならば$ \mathbf{PH} = \mathbf{\Sigma}^p_i
Proof.
$ kに関する帰納法を用いて$ \mathbf{\Sigma}^p_{i+k}, \mathbf{\Pi}^p_{i+k} \subseteq \mathbf{\Sigma}^p_{i} = \mathbf{\Pi}^p_{i}を示せばよい
$ \mathbf{\Sigma}^p_{i+k} = \mathbf{\Pi}^p_{i+k} = \mathbf{\Sigma}^p_{i} = \mathbf{\Pi}^p_{i}を仮定する
$ L \in \mathbf{\Sigma}^p_{i+k+1} \Rightarrow L \in \mathbf{\Sigma}^p_iを示す
仮定より
$ x \in L \iff (\exists u_1 \in 2^{q(|x|)})(\forall u_2 \in 2^{q(|x|)}) ... (\mathsf{Q} u_{i+k+1} \in 2^{q(|x|)})[M(x, u_1, u_2, ... u_{i+k+1}) = 1]
$ L'を次のように定義すると
$ L' := \{\langle x, u_1\rangle\ \ |\ (\forall u_2 \in 2^{q(|x|)}) ... (\mathsf{Q} u_{i+k+1} \in 2^{q(|x|)})M(x, u_1, u_2, ... u_{i+k+1}) = 1 \}
定義より$ L' \in \mathbf{\Pi}^p_{i+k}, 仮定より$ L' \in \mathbf{\Sigma}^p_i
よって
$ \langle x, u_1 \rangle \in L' \iff (\exists u_2 \in 2^{q(|x|)}) ... (\mathsf{Q} u_{i} \in 2^{q(|x|)})[M(x, u_1, u_2, ... u_{i}) = 1]
また$ L'の定義より
$ x \in L \iff (\exists u_1 \in 2^{q(|x|)})[\langle x, u_1 \rangle \in L']
$ \iff (\exists u_1 \in 2^{q(|x|)})(\exists u_2 \in 2^{q(|x|)}) ... (\mathsf{Q} u_{i} \in 2^{q(|x|)})[M(x, u_1, u_2, ... u_{i}) = 1]
$ \iff (\exists u_{12} \in 2^{2q(|x|)}) ... (\mathsf{Q} u_{i} \in 2^{2q(|x|)})[M'(x, u_{12}, ... u_{i}) = 1]
よって$ L \in \mathbf{\Sigma}^p_{i}
$ L \in \mathbf{\Pi}^p_{i+k+1} \Rightarrow L \in \mathbf{\Pi}^p_iを示す
前の結果より
$ L \in \mathbf{\Pi}^p_{i+k+1} \Rightarrow \overline{L} \in \mathbf{\Sigma}^p_{i+k+1} \Rightarrow \overline{L} \in \mathbf{\Sigma}^p_{i} \Rightarrow L \in \mathbf{\Pi}^p_{i} ❏ これは前提が$ \mathbf{\Pi}^p_i \subseteq \mathbf{\Sigma}^p_i（や$ \mathbf{\Sigma}^p_i \subseteq \mathbf{\Pi}^p_i）でもよい
$ L \in \mathbf{\Sigma}^p_i \iff \overline{L} \in \mathbf{\Pi}^p_i \Longrightarrow \overline{L} \in \mathbf{\Sigma}^p_i \iff L = \overline{\overline{L}} \in \mathbf{\Pi}^p_iだから
$ \mathbf{P} = \mathbf{NP}ならば$ \mathbf{PH} = \mathbf{P}
PH完全問題が存在するならばPHはある$ \mathbf{\Sigma}^p_iに崩壊する
Proof.
$ LをPH完全問題だとする
$ L \in \mathbf{PH}よりある$ iが存在して$ L \in \mathbf{\Sigma}^p_i
任意の$ L' \in \mathbf{\Sigma}^p_j ($ j \ge i)は$ LにKarp還元されるので$ L' \in \mathbf{\Sigma}^p_i ❏ $ \mathbf{PH} \subseteq \mathbf{PSPACE}