PP_(計算複雑性理論)とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > PP_(計算複雑性理論)の意味・解説 

PP (計算複雑性理論)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/08/17 10:12 UTC 版)

計算複雑性理論において、複雑性クラス PP とは、確率的チューリング機械多項式時間で解ける決定問題の集合であり、その際に間違う確率は常に 1/2 未満である。PP は 確率的多項式時間 (probabilistic polynomial time) を意味する。1977年、ジョン・ギルが定義した[1]

概要

PP に属する決定問題には、コインを投げて無作為に決定を行うアルゴリズムが存在する。その時間計算量は多項式時間以内であることが保証される。解が YES なら、そのアルゴリズムは 1/2 より高い確率で YES を返す。解が NO なら、そのアルゴリズムは最大でも 1/2 の確率で YES を返す。より実用的な観点では、このクラスに属する問題は、無作為ながらも多項式時間である一定の確率で正しい答えを返すので、それを適当な回数繰り返すことで十分な精度で解を得ることができる。

PP は、非決定性チューリング機械で多項式時間で解ける問題の集合と定義することもでき、その場合、計算経路の半数以上で受理されたとき、全体として受理されたと判断する。このため、PP のことを Majority-P と呼ぶことがある[2]

PP vs BPP

BPPPP部分集合であり、より効率的な乱択アルゴリズムのある部分集合と言える。その違いは間違う確率であり、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と他の複雑性クラスの比較

上述の通り、PPBPP を包含する。

PPNP も包含する。これを証明するには、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のアルゴリズムに決定的な多項式時間多対一還元を前置することができるので、NPPP に含まれることになる。PP補問題英語版について閉じているため、co-NPPP に含まれる。

PPBQP も包含する。BQP量子コンピュータで効率的な多項式時間で解ける決定問題のクラスである。実際、BQPPP に対して英語版である。すなわち、BQP を即座に解ける方法があったとしても PP を解く効率は変わらない。

PP神託機械を持つ多項式時間のチューリングマシン(PPP)は、PH すなわち多項式階層全体に属する全問題を解くことができる。これは戸田誠之助が1989年に示したもので、戸田の定理と呼ばれている。これは PP に属する問題を解くのがいかに困難であるかの証拠である。クラス #P は、P#P = PPP であり、P#PPH を包含するため、PP と同程度に困難と考えられる。

PPTC0 を厳密に包含している。このクラスは回路計算量に関するもので、一定の深さと無制限の入力端子数の論理回路に多数決回路を持っている(Allender 1996, as cited in Burtschick 1999)。

PPPSPACE に包含される。これは MAJSAT 問題を多項式領域で解くアルゴリズムを示せば、容易に証明できる。MAJSAT 問題とは、充足可能問題について、あらゆる組合せを試して、式が真となる組合せを数え上げ、過半数が真なら YES となる問題である。

完全問題とその他の特性

BPPとは異なり、PP意味論的ではなく構文論的なクラスである。任意の確率的機械は、何らかの PP に属する言語を認識する。一方、ある確率的機械の説明を与えられても、それが BPP に属する言語を認識できるかどうかは判定できない。

MAJSAT問題は、PP完全問題である。

PP補集合対称差について閉じており、和集合共通部分についても閉じている[3]。後者2つの証明は前者2つよりずっと難しく、約14年間未解決の問題となっていた。

参考文献

脚注

  1. ^ J. Gill, "Computational complexity of probabilistic Turing machines." SIAM Journal on Computing, 6 (4), pp. 675–695, 1977.
  2. ^ 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
  3. ^ 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.

外部リンク


「PP (計算複雑性理論)」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「PP_(計算複雑性理論)」の関連用語

PP_(計算複雑性理論)のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



PP_(計算複雑性理論)のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのPP (計算複雑性理論) (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS