PP (計算複雑性理論)
計算複雑性理論において、複雑性クラス PP とは、確率的チューリング機械で多項式時間で解ける決定問題の集合であり、その際に間違う確率は常に 1/2 未満である。PP は "probabilistic polynomial time" を意味する。1977年、Gill が定義した[1]。
概要
PP に属する決定問題には、コインを投げて無作為に決定を行うアルゴリズムが存在する。その時間計算量は多項式時間以内であることが保証される。解が YES なら、そのアルゴリズムは 1/2 より高い確率で YES を返す。解が NO なら、そのアルゴリズムは最大でも 1/2 の確率で YES を返す。より実用的な観点では、このクラスに属する問題は、無作為ながらも多項式時間である一定の確率で正しい答えを返すので、それを適当な回数繰り返すことで十分な精度で解を得ることができる。
PP は、非決定性チューリング機械で多項式時間で解ける問題の集合と定義することもでき、その場合、計算経路の半数以上で受理されたとき、全体として受理されたと判断する。このため、PP のことを Majority-P と呼ぶことがある[2]。
PP vs BPP
BPP は PP のサブセットであり、より効率的な乱択アルゴリズムのあるサブセットと言える。その違いは間違う確率であり、BPP は 1/2 以上のある固定の定数 c で示される確率（2/3 とか 501/1000）で正しい解を返さなければならない。この場合、アルゴリズムを繰り返し実行することでチェルノフ限界を使って 1 未満の任意の確率で多数決的に正しい解を得ることができる。c が 1/2 に近いほど繰り返し回数を多くする必要があるが、繰り返し回数は n には依存しない。
重要な点として、定数 c が入力長に依存してはならない。一方、PP アルゴリズムでは以下のようなものが許される。
- YES が正解の場合、YES を確率 1/2+1/2n で返す。このとき n は入力長である。
- NO が正解の場合、YES を確率 1/2 で返す。
これらの確率は非常に近いので（特に n が大きい場合）、何回も繰り返したとしても正解を高い確率で示すのは難しい。多数決方式とチェルノフ限界で、ある確率で正解を示すには、n の指数関数回の繰り返しが必要となる。これは、微妙に細工を施したイカサマのコインを何度も投げて、どちらの面が出やすいかを明らかにするのと似ている。
PPと他の複雑性クラスの比較
上述の通り、PP は BPP を包含する。
PP は NP も包含する。これを証明するには、NP完全問題である充足可能性問題が PP に属することを示せばよい。論理式 F(x1, x2, ..., xn) について無作為に x1, x2, ..., xn の値を決め、それを使って F が真となるか計算してみるアルゴリズムを考える。F が真となったら YES を返し、そうでなければ確率 1/2 で YES、確率 1/2 で NO を返す。
その論理式が充足不可能な場合、このアルゴリズムは YES を確率 1/2 で返す。充足可能な組合せがある場合、YES を返す確率は 1/2 以上である（正確には、充足可能な組合せが得られない場合には 1/2 で、充足可能な組合せが偶然得られた場合は 1 であり、平均すると 1/2 より大きい適当な値となる）。従って、このアルゴリズムは PP に属し、充足可能性問題を解くことができる。SAT（充足可能性問題）はNP完全問題であり、PPのアルゴリズムに決定的な多項式時間多対一還元を前置することができるので、NP は PP に含まれることになる。PP は補問題について閉じているため、co-NP も PP に含まれる。
PP は BQP も包含する。BQP は量子コンピュータで効率的な多項式時間で解ける決定問題のクラスである。実際、BQP は PP に対して low である。すなわち、BQP を即座に解ける方法があったとしても PP を解く効率は変わらない。
PPの神託機械を持つ多項式時間のチューリングマシン（PPP）は、PH すなわち多項式階層全体に属する全問題を解くことができる。これは戸田誠之助が1989年に示したもので、「戸田の定理」と呼ばれている。これは PP に属する問題を解くのがいかに困難であるかの証拠である。クラス #P は、P#P も PH を包含するため、PP と同程度に困難と考えられる。
PP は TC0 を厳密に包含している。このクラスは回路計算量に関するもので、一定の深さと無制限の入力端子数の論理回路に多数決回路を持っている(Allender 1996, as cited in Burtschick 1999)。
PP は PSPACE に包含される。これは MAJSAT 問題を多項式領域で解くアルゴリズムを示せば、容易に証明できる。MAJSAT 問題とは、充足可能問題について、あらゆる組合せを試して、式が真となる組合せを数え上げ、過半数が真なら YES となる問題である。
完全問題とその他の特性
BPPとは異なり、PP は意味論的ではなく文法的なクラスである。任意の確率的機械は、何らかの PP に属する言語を認識する。一方、ある確率的機械の説明を与えられても、それが BPP に属する言語を認識できるかどうかは判定できない。
MAJSAT問題は、PP完全問題である。
PP は補集合と対称差について閉じており、和集合と共通部分についても閉じている[3]。後者2つの証明は前者2つよりずっと難しく、約14年間未解決の問題となっていた。
参考文献
- C. Papadimitriou. Computational Complexity, chapter 11. Addison-Wesley, 1994.
- E. Allender. A note on uniform circuit lower bounds for the counting hierarchy. In Proceedings 2nd International Computing and Combinatorics Conference (COCOON), volume 1090 of Springer Lecture Notes in Computer Science, pages 127-135, 1996.
- Burtschick, Hans-Jörg; Heribert Vollmer (1999年). “Lindström Quantifiers and Leaf Language Definability” (pdf). Electronic Colloquium on Computational Complexity (TR96-005) . 2006年11月20日閲覧..
脚注
- ↑ J. Gill, "Computational complexity of probabilistic Turing machines." SIAM Journal on Computing, 6 (4), pp. 675–695, 1977.
- ↑ Lance Fortnow. Computational Complexity: Wednesday, September 04, 2002: Complexity Class of the Week: PP. http://weblog.fortnow.com/2002/09/complexity-class-of-week-pp.html
- ↑ R. Beigel, N. Reingold, and D. A. Spielman, "PP is closed under intersection", Proceedings of ACM Symposium on Theory of Computing 1991, pp. 1–9, 1991.