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

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

PCP (計算複雑性理論)

(確率的検査可能証明 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/11/14 09:13 UTC 版)

ナビゲーションに移動 検索に移動

計算複雑性理論における PCP とは、確率的検査可能証明(probabilistically checkable proof)系を持つ決定問題複雑性クラスである。

概要と定義

計算複雑性理論において、PCP 系は対話型証明系の一種と見ることができ、証明者がメモリを持たない神託機械であり、検証者が多項式時間の乱択アルゴリズムである。ある言語に属する入力(すなわち答えがYES)の場合、検証者が確実に受理する神託(証明)が存在する。答えがNOの入力の場合、神託がどうであれ、検証者はそれを少なくとも1/2の確率で拒絶する(co-RP参照)。

PCP の別の見方として、NP の強力版と見ることもできる。NPに属する言語について、証明の検証にかかる時間は少なくとも証明にかかる時間程度であるが、PCPに属する言語ではその限りではない。従って、PCPについての証明はNPよりも長くなる可能性がある。

上記の解説では、検証者が神託機械に問い合わせできる回数の上限を特に設定していない。PCP系の能力に影響するもう1つの要因として、検証者が実施できるコイントス回数がある。また、コイントス回数が増えれば、検証者はより厳密に証明を検証できる。従って PCP は実際には、2つの引数を持つ関数でパラメータ化された複雑性クラスのメタクラスと言うことができる。

PCP(r(·), q(·)) は、確率的検査可能証明のある言語のクラスであり、検証者は r(n) 回のコイントスと q(n) 回の神託機械への問い合わせが可能である(n は入力長)。

PCP アルゴリズムの多くは明確に説明するのが困難だが、3CNFSAT のための単純なアルゴリズムの考え方をここで解説する。3CNFSAT とは、各節に必ず3つのリテラルがある連言標準形(CNF)で構成される論理式についての充足可能性問題である。これはNP完全問題である。

m 個の変数と n 個の節からなる論理式 F があるとする。問題は、この論理式を真とするような m 個の変数の値の組合せがあるかどうかである。ただし、ここでは m 個の変数全部を調べるのではなく、O(log n) のランダムビット列で無作為に節を選択する。そして、その節内の変数について、3回の神託機械呼び出しを行って値を得る。それによってその節が真になるなら、検証者がその節を選んだのだから、1/n の確率でそれが真になることを確信できる。このアルゴリズムを n 回繰り返すと、O(nlog n) のランダムビット列と 3n 回の神託機械呼び出しで、ある誤り率を伴いつつ、NP完全問題(さらに全てのNP問題)を PCP(nlog n, n) に置くことができる。

他の複雑性クラスとの関係

単純な特殊ケース(poly は多項式的な量であることを意味し、log は対数的な量であることを意味する):

  • PCP (0, 0) =P
  • PCP (poly, 0) = Co-RP
  • PCP (0, poly) = NP

その他の特筆すべき例:

  • PCP (poly, poly) = NEXP
  • もし NP = PCP (o(log), o(log)) なら NP = P となる。
  • NP = PCP (log, poly)

PCP定理によると、NP = PCP (O(log n), O(1)) である。これは、近似アルゴリズムのために計算困難性を証明するのに役立つ。

外部リンク




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

辞書ショートカット

すべての辞書の索引

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

PCP (計算複雑性理論)のお隣キーワード

PCM音源

PCN

PCNT

PCO

PCOM

PCP

PCP (計算複雑性理論)

PCR

PCS

PCSK9阻害薬

PCSX

PCSX2

PCT

検索ランキング

   

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



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

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのPCP (計算複雑性理論) (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS