NP完整问题的非平凡PCP验证器的示例

Question

在我参与处理NP硬性问题的课程中，我遇到了PCP定理，指出

$ qquad displayStyle Mathsf {np} = Mathsf {pcp}（ log n，1）$。

我了解PCP验证器的技术定义，因此我知道每个NP问题都必须存在哪种算法：一种随机算法，该算法使用$ O来检查给定证书的$ O（1）$位，使用$ O （ log n）$随机位，因此该算法本质上是单侧错误蒙特卡洛验证者。

但是，我很难想象这种算法如何处理NP完整问题。没有阅读PCP定理的证明，是否有此类算法的具体示例？

我浏览了相关部分 计算复杂性：一种现代方法 作者：Arora和Barak（2009），但没有找到任何。

使用$ mathsf {pcp}（ _， ll n）$算法的示例是可以的。

Answer 1

跟进评论 SDCVVC 我检查了示例11.7 in 计算复杂性：一种现代方法 作者：阿罗拉（Arora）和巴拉克（Barak）（草稿 2008年）。在那里，作者描述了问题的“ PCP算法” 图非同构 （GNI）：

输入： 两个图$ g_0 $和$ g_1 $，每个$ n $顶点。

输出： 接受及时仅当$ g_0 $和$ g_1 $不是Isomorph（写$ g_0 not equiv g_1 $）。

我们用$ pi $表示证书（他们称其为“证明”），并用$ pi（i）$ the $ i $ thit $ pi $。

算法$ a $进行如下：

• 在 {0,1 }中选择一个位$ b 随机均匀。
• 在s_n $（$ g_b $的顶点）中选择一个排列$ sigma 。
• 如果$ pi（ langle sigma（g_b） rangle）= b $，请拒绝。

在这里，$ langle _ rangle $是$ mathbb {n}^n $从合适范围$ [0..N] subseteq mathbb {n} $的一些可计算的两者。我们假设，如果不存在$ pi $中的放弃位，即证书太短，我们拒绝。

宣称： 通过上面的算法，GNI在$ operatatorName {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）
3. $（g_0，g_1） notin mathrm {gni} $暗示$ pr [a（g_0，g_1， pi） text {refffect {refforms}] geq geq tfrac {1} {2} {2} {2} {2} {2} 全部 证书$ pi in {0,1 }^*$。

广告1： 从算法中可以清楚地指出，使用$ n log n $随机位可进行统一置换抽样。

广告2： 考虑证书

$ qquad displayStyle pi（ langle h rangle）= begin {case} 0＆，h equiv g_0，h equiv g_1 equiv g_1 1＆，h equiv equiv g_1，h equiv g_1，h equiv g_0 text {intunary}＆， text {否则} end {cases} $

其中$ h $都是带有$ n $节点的图形。由于$ g_0 not equiv g_1 $和$ sigma（g_b） equiv g_b $，我们有$ sigma（g_b） not equiv equiv g_ {1-b} 。因此，查询$ pi $始终产生$ b $，因此始终接受。

广告3： 令$ pi in {0,1 }^*$ nutionary和$ h = sigma（g_b）$所选查询图。如果我们的查询达到了$ pi $的不存在的位，我们是通过假设拒绝的，这是正确的。否则，我们计算

美元＃[h equiv g_0]} + pr [b = 1] cdot frac {＃[ pi（h）= 1 mid h equiv g_1]}} { equiv g_1]} = frac {1} {2} cdot left（ frac {＃[ pi（h）= 0 mid h equiv g_0]} { equiv g_0]} frac {＃[ pi（h）= 1 mid h equiv g_0]}} {＃[h equiv g_0]} right）＆= frac {1} {2} {2} {2} {align} {align} {align} $在这种情况下，使用该$ h equiv g_1 iff h equiv g_0 $。

因此，索赔得到了证明。

---

一些有助于我更好地掌握这些概念的观察结果。

• 证书$ pi $可以任意且任意复杂。请注意，上述算法的“好”证书基本上解决了与该算法相同的问题（多次）。
• 但这并不意味着可以通过“仅在证书中提供答案”来以PCP样式解决任何决策问题。条件3阻止了这种天真的尝试。
• 通常，不可能得出一个猜测证书的有效（随机的单侧错误）算法（NP-Certificate验证者的情况）。

---

1. 严格来说，这是假设$ n！= 2^k $（当然几乎永远不会容纳），因为我们 有无限最差的运行时间 对于其他$ n $。但是，Arora/Barak似乎忽略了这一方面。

Answer 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

琐事：第一个练习归于GNI的PCP，而第二个练习则是永久性的PCP。这两个结果均由$ mathsf {nexp} = Mathsf {pcp}（ text {poly}（n），1）$累及。