NP不完全な問題のための非自明のPCP検証の例

Question

NPハードの問題に対処するためのコースに参加している間、私はPCP定理に遭遇し、述べています

$ qquad displaystyle mathsf {np} = mathsf {pcp}（ log n、1）$。

私はPCP検証剤の技術的定義を理解しているので、原則として、すべてのNP問題に対してどのようなアルゴリズムが存在するかを知っています。 （ log n）$ランダムビット。そのため、このアルゴリズムは本質的に片側エラーモンテカルロ検証剤です。

ただし、このようなアルゴリズムがNP完全な問題にどのように対処できるかを想像するのに苦労しています。 PCP定理の証拠を読む以外に、そのようなアルゴリズムに具体的な例はありますか？

の関連するセクションをスキムしました 計算の複雑さ：現代のアプローチ Arora and Barak（2009）は何も見つかりませんでした。

$ mathsf {pcp}（ _、 ll n）$ algorithmを使用した例では問題ありません。

Answer 1

によるコメントのフォローアップ SDCVVC 例11.7インチをチェックしました 計算の複雑さ：現代のアプローチ アロラとバラクによる（下書き 2008年）。そこで、著者は問題の「PCPアルゴリズム」について説明しています 非異形グラフ （GNI）：

入力： 2つのグラフ$ g_0 $と$ g_1 $ $ n $ verticesそれぞれ。

出力： $ g_0 $と$ g_1 $がIsomorphではない場合にのみ受け入れます（$ g_0 not equiv $ $を書き込みます）。

証明書を$ pi $ by by $ pi（i）$ $ i $ -th Bit of $ pi $で示します。

アルゴリズム$ a $は次のように進行します。

• ランダムに均一に均一に$ b in {0,1 }を選択します。
• s_n $（$ g_b $の頂点）の順列$ sigma を選択します。
• $ pi（ langle sigma（g_b） rangle）= b $の場合は、それ以外の場合は拒否します。

ここでは、$ langle _ rangle $は、$ mathbb {n}^n $から適切な範囲$ [0..n] Subseteq Mathbb {n} $への計算可能な分割です。 $ pi $の逆のビットが存在しない場合、つまり証明書が短すぎると拒否されます。

請求： 上記のアルゴリズムにより、gniは$ operatorname {pcp}（n log n、1）$にあります。

1. アルゴリズムは$ o（n log n）$ランダムビットとクエリを使用します$ o（1）$ pi $、
2. $（g_0、g_1） in mathrm {gni} $は、証明書$ pi $があるため、$ pr [a（g_0、g_1、 pi） text {Accepts}] = 1 $、および1 $、および
3. $（g_0、g_1） notin mathrm {gni} $は、$ pr [a（g_0、g_1、 pi） text {redjects}] geq tfrac {1} {2} $ $ for すべて 証明書$ pi in {0,1 }^*$。

広告1： $ log n $ランダムビットで均一な順列サンプリングが可能であることに注意することにより、アルゴリズムからクリア。

広告2： 証明書を検討してください

$ qquad displaystyle pi（ langle h rangle）= begin {cases} 0＆、h equiv g_0、h text {arbitrary}＆、 text {それ以外の} end {cases} $

ここで、$ h $はすべて$ n $ノードのあるグラフです。 $ g_0 not equiv g_1 $ and $ sigma（g_b） equiv g_b $であるため、$ sigma（g_b） not equiv g_ {1-b} $ forすべての$ b $および$ sigma $ 。したがって、$ pi $へのクエリは常に$ b $を生成し、したがって常に受け入れます。

広告3： $ pi in {0,1 }^*$ arbitraryおよび$ h = sigma（g_b）$選択したクエリグラフをクエリが存在しない$ pi $のビットにヒットした場合、仮定によって拒否されます。これは正しいです。それ以外の場合は、計算します

$ qquad begin {align} pr [ text {accept}]＆= pr [b = 0] cdot frac {＃[ pi（h）= 0 mid h equiv g_0]} { ＃[h equiv g_0]} + pr [b = 1] cdot frac {＃[ pi（h）= 1 mid h equiv g_1]} {＃[H equiv g_1]} ＆= frac {1} {2} cdot left（ frac {＃[ pi（h）= 0 mid h equiv g_0]} {＃[H equiv g_0]} + frac {＃[ pi（h）= 1 mid h equiv g_0]} {＃[h equiv g_0]} right）＆= frac {1} {2} end {align}この場合、$ h equiv g_1 iff h equiv g_0 $を使用しています。

したがって、クレームは証明されています。

---

私がこれらの概念をよりよく理解するのに役立ついくつかの観察結果。

• 証明書$ pi $は、任意に長く、任意に複雑になる可能性があります。上記のアルゴリズムの「良い」証明書は、本質的にアルゴリズムと同じ問題を解決することに注意してください（何度も）。
• しかし、それは、「証明書に答えを提供するだけ」で、決定の問題をPCPスタイルで解決できることを意味するものではありません。条件3は、その種の素朴な試みを防ぎます。
• 一般的に、証明書を推測する効率的な（無作為化片面誤差）アルゴリズムを導き出すことはできません（NP認証検証剤の場合と同様）。

---

1. 厳密に言えば、これは$ n！= 2^k $（もちろん、ほとんど保持されない）を想定しています。 無限の最悪のランタイムがあります その他の$ n $の場合。しかし、アロラ/バラクはこの側面を無視しているようです。

Answer 2

直観の開発に役立つ可能性のある2つの問題：

1. $ mathsf {am} subseteq mathsf {pcp}（ text {poly}（n）、1）$であることを証明します。 $ mathsf {np} subseteq mathsf {pcp}（ text {poly}（n）、1）$を想定することができます。

2. $ mathsf {pspace} subseteq mathsf {pcp}（ text {poly}（n）、 text {poly}（n））$を証明します。ヒント：

IP = PSPACEを使用します

Trivia：最初のエクササイズはGNIのPCPを包含し、2番目はPCPを永続的に包含します。両方の結果は、$ mathsf {nexp} = mathsf {pcp}（ text {poly}（n）、1）$によって包含されます。