PP（複雑さ）

複雑性理論において、PPまたはPPTは、確率的チューリングマシンによって多項式時間で解ける決定問題のクラスであり、すべてのインスタンスのエラー確率は1/2未満です。略語PPは確率多項式時間を表します。複雑性クラスは1977年にギルによって定義されました。^[1]

決定問題がPPに含まれる場合、コインを投げてランダムな決定を下すことが可能なアルゴリズムが存在します。このアルゴリズムは多項式時間で実行されることが保証されています。答えが YES の場合、アルゴリズムは 1/2 を超える確率で YES と答えます。答えが NO の場合、アルゴリズムは 1/2 未満の確率で YES と答えます。より実際的な言葉で言えば、これは、ランダム化された多項式時間アルゴリズムを十分な回数 (ただし制限付き) 実行することで、任意の固定精度で解決できる問題のクラスです。

多項式的に制限され確率的なチューリングマシンは、確率的多項式時間マシンの略であるPPTとして特徴付けられます。 ^[2]このチューリングマシンの特徴付けでは、制限されたエラー確率は必要ありません。したがって、PP は、エラー確率が 1/2 未満の PPT マシンで解決可能なすべての問題を含む複雑性クラスです。

PPの別の特徴付けは、非決定性チューリングマシンによって多項式時間で解くことができる問題の集合であり、その受理条件は計算パスの過半数（半分以上）が受理することである。このため、一部の著者はMajority-Pという別名を提案している。^[3]

言語LがPPに属する場合、そしてその場合のみ、確率チューリングマシンM が存在し、

• Mはすべての入力に対して多項式時間で実行される
• L内のすべてのxに対して、M は1/2以上の確率で1を出力する。
• Lに含まれないすべてのxに対して、M は1/2 未満の確率で 1 を出力します。

あるいは、PPは決定性チューリングマシンのみを使用して定義することもできます。言語LがPPに属するのは、多項式pと決定性チューリングマシンMが存在し、

• Mはすべての入力に対して多項式時間で実行される
• L内のすべてのxについて、長さp (| x |)の文字列yのうちM(x,y) = 1 を満たすものの割合は1/2 より大きい。
• Lに含まれないすべてのxについて、長さp (| x |)の文字列yのうちM(x,y) = 1を満たすものの割合は1/2未満です。

どちらの定義でも、「未満」は「以下」に変更でき（下記参照）、しきい値 1/2 は、クラスを変更せずに (0,1) 内の任意の固定有理数に置き換えることができます。

BPPはPPのサブセットです。効率的な確率アルゴリズムが存在するサブセットと見なすことができます。違いは許容されるエラー確率にあります。 BPPでは、アルゴリズムは 2/3 や 501/1000 など、固定定数 c > 1/2 を超える確率で正しい答え (YES または NO) を返す必要があります。この場合、アルゴリズムを複数回実行し、多数決をとることで、チェルノフ境界を使用して 1 未満の任意の正しい確率を達成できます。この繰り返し回数はc が1/2 に近づくと増加しますが、入力サイズnには依存しません。

より一般的には、c がのように入力サイズ多項式に依存できる場合、に対してアルゴリズムを再実行し、多数決を取ることができます。Hoeffding の不等式により、これによりBPPアルゴリズムが得られます。 ${\displaystyle n}$${\displaystyle c=O(n^{-k})}$${\displaystyle O(n^{2k})}$

重要なことは、この定数cが入力に依存できないことです。一方、PPアルゴリズムでは次のようなことが許可されています。

• YES インスタンスでは、確率 1/2 + 1/2 ⁿで YES を出力します。ここで、n は入力の長さです。
• NOインスタンスの場合、確率1/2 − 1/2 ⁿでYESを出力します。

これら 2 つの確率は指数関数的に接近しているため、多項式回数実行したとしても、YES インスタンスを操作しているのか、NO インスタンスを操作しているのかを判断するのは非常に困難です。多数決とチェルノフ境界を使用して、固定された目的の確率レベルを達成しようとすると、nの指数関数的な回数の繰り返しが必要になります。

PPにはBPPが含まれます。これは、 BPPの定義で説明されている確率的アルゴリズムがPPの定義の確率的アルゴリズムのサブセットを形成するためです。

PP にはNPも含まれます。これを証明するために、NP 完全な 充足可能性問題がPPに属することを示します。式F ( x ₁、  x ₂、...、  x _n ) が与えられたときに、割り当てx ₁、  x ₂、...、  x _{n を}一様にランダムに選択する確率アルゴリズムを考えます。次に、アルゴリズムは割り当てによって式F が真になるかどうかを確認します。真になる場合は、YES を出力します。そうでない場合は、確率 で YES を出力し、確率 で NO を出力します。 ${\displaystyle {\frac {1}{2}}-{\frac {1}{2^{n+1}}}}$${\displaystyle {\frac {1}{2}}+{\frac {1}{2^{n+1}}}}$

式が満たされない場合、アルゴリズムは常に確率 で YES を出力します。満たされる割り当てが存在する場合、少なくとも確率 （満たされない割り当てを選択した場合は正確に 1/2 、満たされる割り当てを選択した場合は 1 で、平均すると 1/2 より大きい数になります）で YES を出力します。したがって、このアルゴリズムはPPに満足可能性を含めます。SAT は NP 完全であり、任意の決定論的多項式時間の多対一縮約をPPアルゴリズムにプレフィックスできるため、NPはPPに含まれます。PPは補集合に対して閉じているため、 co-NPも含まれます。 ${\displaystyle {\frac {1}{2}}-{\frac {1}{2^{n+1}}}<{\frac {1}{2}}}$${\displaystyle \left({\frac {1}{2}}-{\frac {1}{2^{n+1}}}\right)\cdot \left(1-{\frac {1}{2^{n}}}\right)+1\cdot {\frac {1}{2^{n}}}={\frac {1}{2}}+{\frac {1}{2^{2n+1}}}>{\frac {1}{2}}}$

さらにPPにはMA ^[4]が含まれており、これは前述の2つの包含を包含しています。

PP には、効率的な多項式時間量子コンピュータで解ける決定問題のクラスであるBQPも含まれます。実際、 BQP はPPに対して低いため、PPマシンはBQP問題を瞬時に解くことができることから何の利益も得られません。事後選択を備えた量子コンピュータ上の多項式時間のクラスであるPostBQPは、PPに等しいです^[5] (下記の #PostBQP を参照)。

さらに、PP にはQMAが含まれ、これはMAとBQPの包含を包含します。

PPオラクル( P ^PP )を備えた多項式時間チューリングマシンは、PH 、つまり多項式階層全体のすべての問題を解くことができます 。この結果は1989 年に戸田誠之助によって示され、戸田の定理として知られています。これは、PPの問題を解決するのがいかに難しいかを示しています。クラス#Pは、 P ^#P = P ^PPであり、したがってP ^#PにはPHも含まれるため、ある意味ではほぼ同じくらい難しいです。^[6]

PPは、均一な多数決ゲート（多項式時間アルゴリズムによって生成される）を持つ定数深さ、無制限ファンインブール回路のクラスである均一TC0^{を厳密に含みます。 [7]}

PPはPSPACEに含まれています。これは、以下で定義されるMAJSATの多項式空間アルゴリズムを示すことで簡単に示せます。すべての割り当てを試して、条件を満たすものの数を数えるだけです。

カンナンの定理によれば、 PPは任意のkに対してSIZE (n ^k )に含まれません。

BPPとは異なり、PP は意味クラスではなく構文クラスです。任意の多項式時間確率マシンはPP内の何らかの言語を認識します。対照的に、多項式時間確率マシンの説明が与えられた場合、それがBPP内の言語を認識するかどうかを判断することは一般には決定不可能です。

PPにはMAJSATのような自然完全問題があります。^[1] MAJSATはブール式Fが与えられたときの決定問題です。すべての割り当てx ₁、  x ₂、...、  x _nの半分以上がFを真にする場合は答えがYESで、そうでない場合は答えがNOになります。

L をPPの言語とする。Lの補集合を で表す。PPの定義により、次の性質を持つ 多項式時間確率アルゴリズムAが存在する。${\displaystyle L^{c}}$

${\displaystyle x\in L\Rightarrow \Pr[A{\text{ accepts }}x]>{\frac {1}{2}}\quad {\text{and}}\quad x\not \in L\Rightarrow \Pr[A{\text{ accepts }}x]\leq {\frac {1}{2}}.}$

一般性を失うことなく、後者の不等式は常に厳密であると主張する。この主張から定理が導かれる。Aが拒否する時にAが受け入れるという点を除いてAと同じマシンを とすると、逆もまた同様である。すると ${\displaystyle A^{c}}$${\displaystyle A^{c}}$

${\displaystyle x\in L^{c}\Rightarrow \Pr[A^{c}{\text{ accepts }}x]>{\frac {1}{2}}\quad {\text{and}}\quad x\not \in L^{c}\Rightarrow \Pr[A^{c}{\text{ accepts }}x]<{\frac {1}{2}},}$

これはPP内にあることを意味します。 ${\displaystyle L^{c}}$

ここで、一般性を損なうことなく仮定を正当化します。 を入力xに対するAの実行時間の多項式上限とします。したがって、A は実行中に最大でランダムにコインを投げます。特に、受理確率は の整数倍であり、次の式が成り立ちます。 ${\displaystyle f(|x|)}$${\displaystyle f(|x|)}$${\displaystyle 2^{-f(|x|)}}$

${\displaystyle x\in L\Rightarrow \Pr[A{\text{ accepts }}x]\geq {\frac {1}{2}}+{\frac {1}{2^{f(|x|)}}}.}$

マシンA ′を次のように定義する。入力xに対して、A ′はAをサブルーチンとして実行し、Aが拒否する場合は拒否する。そうでない場合、Aが受け入れる場合は、A ′はコインを投げ、すべて表であれば拒否し、そうでない場合は受け入れる。そして、 ${\displaystyle f(|x|)+1}$

${\displaystyle x\not \in L\Rightarrow \Pr[A'{\text{ accepts }}x]\leq {\frac {1}{2}}\cdot \left(1-{\frac {1}{2^{f(|x|)+1}}}\right)<{\frac {1}{2}}}$

そして

${\displaystyle x\in L\Rightarrow \Pr[A'{\text{ accepts }}x]\geq \left({\frac {1}{2}}+{\frac {1}{2^{f(|x|)}}}\right)\cdot \left(1-{\frac {1}{2^{f(|x|)+1}}}\right)>{\frac {1}{2}}.}$

これにより仮定が正当化され（A ′ は依然として多項式時間確率アルゴリズムであるため）、証明が完了します。

デイビッド・ルッソは1985年の博士論文^[8]で、対称差に関してPPが閉じていることを証明した。PPが和集合と積集合に関して閉じているかどうかは14年間未解決だったが、ベイゲル、ラインゴールド、スピルマンによって肯定的に解決された。^{[9]その後、リー[10]}とアーロンソンによって別の証明が与えられた（下記の#PostBQPを参照）。

量子計算量クラスBQP は、量子チューリングマシンで多項式時間で解ける問題のクラスです。事後選択を追加することで、 PostBQPと呼ばれるより大きなクラスが得られます。非公式には、事後選択はコンピュータに次の力を与えます。何らかのイベント (特定の状態の量子ビットの測定など) がゼロ以外の確率を持つときはいつでも、それが起こると想定できます。^[11]スコット・アーロンソンは、 2004 年にPostBQPがPPに等しいことを示しました。^{[5] [12]}このPPの再定式化により、 PP は交差 (したがって和集合) に関して閉じていること、BQP はPPに対して低いこと、QMA はPPに含まれることなど、特定の結果を示すことが容易になります。

PP はPQPと呼ばれる別の量子計算量クラスとも等しく、これはBQPの無制限誤差類似体である。これは量子コンピュータが多項式時間で解ける決定問題のクラスを表し、すべてのインスタンスで誤差確率は 1/2 未満である。PQP 計算に使用されるすべての振幅が代数的数から抽出されたとしても、 PQPはPPと一致する。^[13]

• Papadimitriou, C. (1994) 「第 11 章」計算の複雑さ. Addison-Wesley.。
• Allender, E. (1996)。「カウンティング階層の均一回路下限に関する注記」。第 2 回国際コンピューティングおよび組合せ論会議 (COCOON) の議事録。コンピュータ サイエンスの講義ノート。第 1090 巻。Springer-Verlag。pp. 127–135。。
• Burtschick, Hans-Jörg; Vollmer, Heribert (1998). 「Lindström 量指定子と葉言語の定義可能性」. Int. J. Found. Comput. Sci . 9 (3): 277–294. doi :10.1142/S0129054198000180. ECCC  TR96-005.

• 複雑動物園：PP