PCP定理

計算複雑性理論において、PCP 定理( PCP 特性定理とも呼ばれる) は、NP 複雑性クラスのすべての決定問題には、一定のクエリ複雑性と対数ランダム性複雑性 (対数数のランダムビットを使用) の確率的に検証可能な証明(ランダム化アルゴリズムによって検証できる証明)があることを述べています。

PCP 定理は、ある普遍定数Kについて、あらゆるnに対して、長さnのステートメントに対する任意の数学的証明は、その証明のK文字のみを検査するランダム化アルゴリズムによって 99% の精度で形式的に検証可能な、長さ poly( n )の異なる証明として書き直すことができるというものです。

PCP定理は、近似の計算困難性の理論の基礎であり、さまざまな最適化問題に対する効率的な近似アルゴリズムの設計の固有の困難さを調査します。インゴ・ウェゲナーはこれを「クックの定理以来の計算量理論における最も重要な結果」^[1]と評し、オデッド・ゴールドライヒはこれを「革新的なアイデアに富んだ一連の印象的な研究の集大成」^{[2]と評しました。}

正式な声明

PCP定理は、

NP = PCP [O(log n ), O(1)],

ここで、PCP [ r ( n ), q ( n )] は、確率的に検証可能な解決の証明を与えることができる問題のクラスであり、その証明はr ( n ) ビットのランダム性を使用して多項式時間で検証でき、 q ( n ) ビットの証明を読み取ることで、正しい証明は常に受け入れられ、間違った証明は少なくとも 1/2 の確率で拒否されます。nは、問題インスタンスの記述のビット単位の長さです。さらに、検証アルゴリズムは非適応型であることに注意してください。つまり、チェックする証明のビットの選択は、証明の実際のビットではなく、ランダムビットと問題インスタンスの記述のみに依存します。

PCPと近似の難しさ

PCP定理の別の定式化では、制約充足問題における充足可能な制約の最大割合を、ある定数倍の範囲内で近似することはNP困難であると述べられている。^[3]

正式には、定数qおよびα < 1 に対して、次の約束問題( L _yes、L _no ) は NP 困難な決定問題です。

L _yes = {Φ: Φ 内のすべての制約は同時に満たすことができる}
L _no = {Φ: すべての割り当てはΦの制約のα分数未満を満たす}、

ここで、Φ は、制約ごとに最大q 個の変数を持つブールアルファベット上の制約充足問題(CSP)です。

前述のPCPクラスとの関連は、証明内の定数ビットqをチェックすることは、証明のそれらのビットに対するqブール変数の制約を評価することと見なすことができることに気付くことによって理解できます。検証アルゴリズムはO (log n ) ビットのランダム性を使用するため、上で説明したように、 poly ( n ) 制約を持つ CSP として表すことができます。PCP 定理のもう 1 つの特徴付けは、α = 1/2 の約束条件を保証します。NP 問題の答えが「はい」の場合、すべての制約 (ランダムビットの特定の値に対応) には、満足のいく割り当て (受け入れ可能な証明) があります。それ以外の場合、すべての証明は少なくとも 1/2 の確率で拒否される必要があります。つまり、すべての割り当ては、制約の 1/2 未満を満たす必要があります (つまり、1/2 未満の確率で受け入れられる)。したがって、約束の問題のアルゴリズムは、基礎となる NP 問題を解決できるため、約束の問題は NP 困難である必要があります。

この定理の結果として、最大ブール式充足可能性、グラフの最大独立集合、格子の最短ベクトル問題など、多くの自然な最適化問題の解は、 P = NPでない限り効率的に近似できないことが示されます。これは、このような問題の解を近似する問題を、上記の形式の約束問題に縮小することによって行うことができます。これらの結果は、何らかの追加構造を持つ NP の確率的に検証可能な証明と見なすことができるため、 PCP 定理と呼ばれることもあります。

証拠

より弱い結果の証明は、デクスター・ ${\mathsf {NP}}\subseteq {\mathsf {PCP}}[n^{3},1]$ コーゼンの講義の一つで与えられている。^[4]

歴史

PCP 定理は、対話型証明と確率的に検証可能な証明に関する長年の研究の集大成です。標準証明と確率的に検証可能な証明を関連付ける最初の定理は、 NEXP ⊆ PCP [poly( n ), poly( n )] というステートメントであり、Babai、Fortnow、Lund (1990) によって証明されました。

頭文字の由来

表記法PCP _{c ( n ), s ( n )} [ r ( n ), q ( n )] は確率的に検証可能な証明で説明されています。この表記法は、特定の複雑性クラスを返す関数の表記法です。上記の説明を参照してください。

この定理の名前 (「PCP 定理」) は、おそらく「確率的に検証可能な証明」を意味する「PCP」、または上記の表記法 (あるいはその両方) に由来しています。

最初の定理 [1990年]

その後、この研究で使用された方法は、1991 年に Babai、Lance Fortnow、Levin、および Szegedy (Babai et al. 1991)、Feige、Goldwasser、Lund、Safra、および Szegedy (1991)、および 1992 年に Arora と Safra (Arora & Safra 1992) によって拡張され、1998 年に Arora、Lund、Motwani、Sudan、および Szegedy によって PCP 定理の証明が得られました (Arora et al. 1998)。

2001 年のゲーデル賞は、 PCP 定理と近似困難性との関係に関する研究に対して、サンジーヴ・アローラ、ウリエル・ファイギ、シャフィ・ゴールドヴァッサー、カールステン・ルンド、ラースロー・ロヴァース、ラジーヴ・モトワニ、シュムエル・サフラ、マドゥ・スーダン、マリオ・セゲディに授与されました。

2005年にイリット・ディヌールは、エクスパンダーグラフを用いてPCP定理のはるかに単純な証明を発見した。^[5]彼女はこの功績により2019年のゲーデル賞を受賞した。^[6]

量子アナログ

2012年、トーマス・ヴィディックと伊藤剛は、「マルチプレイヤーゲームでエンタングルド証明者が共謀する能力には強い制限がある」ことを示す結果^{[7]を発表しました。これは、PCP定理の量子アナログを証明するための一歩となる可能性があります。なぜなら、結果}^[7]がメディアで報道されたとき、^[8]^[9]、ドリット・アハロノフ教授は、これを「基本的にPCP定理につながった、マルチ証明者インタラクティブ証明に関する以前の論文の量子アナログ」と呼んだからです。^[9]

2018年、トーマス・ヴィディックとアナンド・ナタラジャンは、ランダム化還元の下での量子PCP定理のゲーム版を証明した^{[10] 。これは、} $QMA \subseteq MIP * [log(n), 1, 1/2]$ であると述べています。ここで、 $MIP * [f (n), c, s]は、$ f ( n )ビットの古典的通信を備えたマルチ証明者量子対話型証明システムの複雑性クラスであり、完全性はcで健全性はsです。彼らはまた、量子PCP予想のハミルトンバージョン、つまり定数プロミスギャップ $c - s$ を持つローカルハミルトン問題がQMA困難であることを示し、ゲーム量子PCP定理を意味しています。

NLTS予想は根本的な未解決の障害であり、PCPの量子類似体の先駆けであった。^[11] NLTS予想は2022年にAnurag Anshu、Nikolas Breuckmann、Chinmay Nirkheによって証明された。^[12]

注記

^ インゴ・ウェゲナー (2005)。複雑性理論：効率的なアルゴリズムの限界を探る。シュプリンガー。p. 161。ISBN 978-3-540-21045-0。
^ Oded Goldreich (2008). 計算複雑性: 概念的視点. Cambridge University Press. p. 405. ISBN 978-0-521-88473-0。
^ Arora, Sanjeev; Barak, Boaz (2009). 計算複雑性: 現代的アプローチ(PDF) (ドラフト). Cambridge University Press.
^ コゼン、デクスター C. (2006)。計算理論。コンピューターサイエンスのテキスト。ロンドン: Springer-Verlag。 119–127ページ。ISBN 9781846282973。
^ 2005 年のプレプリント、ECCC TR05-046 を参照。この論文の信頼できるバージョンは Dinur (2007) です。
^ EATSC 2019 Gödel Prize、2019年9月11日閲覧。
^ ab 伊藤剛; Vidick, Thomas (2012). 「エンタングルド証明器に対する NEXP サウンドのマルチ証明器インタラクティブ証明」第53 回 IEEE コンピュータサイエンス基礎シンポジウム、FOCS 2012、ニューブランズウィック、ニュージャージー、米国、2012 年 10 月 20 ～23日。IEEEコンピュータ協会。pp . 243 ～ 252。arXiv : 1207.0550。doi :10.1109/FOCS.2012.11。ISBN 978-0-7695-4874-6。
^ Hardesty, Larry (2012-07-30). 「MIT ニュースリリース: 理論計算機科学における 10 年来の問題が解消」. MIT ニュースオフィス。2014 年 2 月 2 日時点のオリジナルからアーカイブ。2012年 8 月 10 日閲覧。対話型証明は現在広く使用されている暗号システムの基礎ですが、計算機科学者にとっては、計算問題の複雑さに関する洞察を提供するという点でも同様に重要です。
^ ab Hardesty, Larry (2012-07-31). 「理論計算機科学における10年来の問題が解消」。MITニュースオフィス。2012-08-01にオリジナルからアーカイブ。2012-08-10に取得。エルサレムのヘブライ大学の計算機科学および工学教授であるDorit Aharonov氏は、Vidick氏とIto氏の論文は、マルチ証明者対話型証明に関する以前の論文の量子版であり、「基本的にPCP定理につながった。そして、PCP定理は間違いなく過去20年間の複雑性に関する最も重要な結果である」と述べている。同様に、彼女は、新しい論文は「量子複雑性理論における主要な未解決問題であるPCP定理の量子版を証明するための重要な一歩となる可能性がある」と述べている。
^ Natarajan, A.; Vidick, T. (2018 年 10 月)。「量子状態の低次テストと QMA 用の量子エンタングルドゲーム PCP」。2018 IEEE第59 回コンピュータサイエンスの基礎に関する年次シンポジウム (FOCS)。pp. 731–742。arXiv : 1801.03821。Bibcode : 2018arXiv180103821N。doi : 10.1109 / FOCS.2018.00075。ISBN 978-1-5386-4230-6. S2CID 53062680。
^ 「NLTS予想について」。Simons Institute for the Theory of Computing。2021年6月30日。 2022年8月8日閲覧。
^ Anshu, Anurag; Breuckmann, Nikolas P .; Nirkhe, Chinmay ( 2023). 「優れた量子コードからのNLTSハミルトニアン」。第55回ACMコンピューティング理論シンポジウムの議事録。pp. 1090–1096。arXiv ：2206.13228。doi：10.1145 / 3564246.3585114。ISBN 9781450399135. S2CID 250072529。

参考文献

Arora, サンジーヴ;ルンド, カーステン;モトワニ, ラジーブ;スーダン, マドゥ; Szegedy、Mario (1998)、「証明の検証と近似問題の難しさ」、Journal of the ACM、45 (3): 501–555、doi :10.1145/278298.278306、S2CID 8561542。
アローラ、サンジーヴ、サフラ、シュムエル(1992)、「近似クリークは NP 完全である」、第 33 回 IEEE コンピュータサイエンス基礎シンポジウムの議事録、41 (1): 2–13
アローラ、サンジーヴ、サフラ、シュムエル(1998)、「証明の確率的検証：NP の新しい特徴付け」、Journal of the ACM、45 (1): 70–122、doi : 10.1145/273865.273901、S2CID 751563。
ババイ、ラースロー、フォートナウ、ランス、レビン、レオニード、セゲディ、マリオ(1991)、「ポリログ時間での計算のチェック」、STOC '91: 第 23 回 ACM コンピューティング理論シンポジウムの議事録、ACM、pp. 21–32、ISBN 978-0-89791-397-3。
Babai, László ; Fortnow, Lance ; Lund, Carsten (1990)、「非決定性指数時間には 2 つの証明者対話型プロトコルがある」、SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer Science、IEEE Computer Society、pp. 16–25、ISBN 978-0-8186-2082-9。
Dinur、Irit (2007)、「ギャップ増幅による PCP 定理」、Journal of the ACM、54 (3): 12–es、doi :10.1145/1236457.1236459、S2CID 53244523。
ファイギ, ウリエル; Goldwasser, シャフィ州; Lovász, ラスロー;サフラ, シュムエル; Szegedy、Mario (1996)、「対話型証明と近似クリークの硬度」(PDF)、Journal of the ACM、43 (2)、ACM: 268–292、doi : 10.1145/226643.226652、ISSN 0004-5411。

[Wegener2005-1] インゴ・ウェゲナー (2005)。複雑性理論：効率的なアルゴリズムの限界を探る。シュプリンガー。p. 161。ISBN 978-3-540-21045-0。

[Goldreich2008-2] Oded Goldreich (2008). 計算複雑性: 概念的視点. Cambridge University Press. p. 405. ISBN 978-0-521-88473-0。

[CompComplMA-3] Arora, Sanjeev; Barak, Boaz (2009). 計算複雑性: 現代的アプローチ(PDF) (ドラフト). Cambridge University Press.

[4] コゼン、デクスター C. (2006)。計算理論。コンピューターサイエンスのテキスト。ロンドン: Springer-Verlag。 119–127ページ。ISBN 9781846282973。

[5] 2005 年のプレプリント、ECCC TR05-046 を参照。この論文の信頼できるバージョンは Dinur (2007) です。

[6] EATSC 2019 Gödel Prize、2019年9月11日閲覧。

[LANL_Vidick_Ito-7] 伊藤剛; Vidick, Thomas (2012). 「エンタングルド証明器に対する NEXP サウンドのマルチ証明器インタラクティブ証明」第53 回 IEEE コンピュータサイエンス基礎シンポジウム、FOCS 2012、ニューブランズウィック、ニュージャージー、米国、2012 年 10 月 20 ～23日。IEEEコンピュータ協会。pp . 243 ～ 252。arXiv : 1207.0550。doi :10.1109/FOCS.2012.11。ISBN 978-0-7695-4874-6。

[eurekalert_2012-July_30-8] Hardesty, Larry (2012-07-30). 「MIT ニュースリリース: 理論計算機科学における 10 年来の問題が解消」. MIT ニュースオフィス。2014 年 2 月 2 日時点のオリジナルからアーカイブ。2012年 8 月 10 日閲覧。対話型証明は現在広く使用されている暗号システムの基礎ですが、計算機科学者にとっては、計算問題の複雑さに関する洞察を提供するという点でも同様に重要です。

[MIT_newsoffice_2012_July_31-9] Hardesty, Larry (2012-07-31). 「理論計算機科学における10年来の問題が解消」。MITニュースオフィス。2012-08-01にオリジナルからアーカイブ。2012-08-10に取得。エルサレムのヘブライ大学の計算機科学および工学教授であるDorit Aharonov氏は、Vidick氏とIto氏の論文は、マルチ証明者対話型証明に関する以前の論文の量子版であり、「基本的にPCP定理につながった。そして、PCP定理は間違いなく過去20年間の複雑性に関する最も重要な結果である」と述べている。同様に、彼女は、新しい論文は「量子複雑性理論における主要な未解決問題であるPCP定理の量子版を証明するための重要な一歩となる可能性がある」と述べている。

[10] Natarajan, A.; Vidick, T. (2018 年 10 月)。「量子状態の低次テストと QMA 用の量子エンタングルドゲーム PCP」。2018 IEEE第59 回コンピュータサイエンスの基礎に関する年次シンポジウム (FOCS)。pp. 731–742。arXiv : 1801.03821。Bibcode : 2018arXiv180103821N。doi : 10.1109 / FOCS.2018.00075。ISBN 978-1-5386-4230-6. S2CID 53062680。

[11] 「NLTS予想について」。Simons Institute for the Theory of Computing。2021年6月30日。 2022年8月8日閲覧。

[12] ^ Anshu, Anurag; Breuckmann, Nikolas P .; Nirkhe, Chinmay ( 2023). 「優れた量子コードからのNLTSハミルトニアン」。第55回ACMコンピューティング理論シンポジウムの議事録。pp. 1090–1096。arXiv ：2206.13228。doi：10.1145 / 3564246.3585114。ISBN 9781450399135. S2CID 250072529。