多項式階層内の問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/13 15:58 UTC 版)
Σ 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}}} について完全である。
※この「多項式階層内の問題」の解説は、「多項式階層」の解説の一部です。
「多項式階層内の問題」を含む「多項式階層」の記事については、「多項式階層」の概要を参照ください。
- 多項式階層内の問題のページへのリンク
