本文主要是介绍PCP的Parallel Repetition，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 引言
见Alessandro Chiesa等人2023年论文《On Parallel Repetition of PCPs》。
Parallel Repetition（并行重复）可用于：
- 降低probabilistic proofs的soundness error 的同时
- 提升某些衡量指标的效率
interactive proofs（IPs）和multi-prover interactive proofs（MIPs）均由研究并行重复。本文首创对probabilistically checkable proofs（PCPs）研究并行重复。
本文的研究结论为：
- PCP的并行重复会增加soundness error——随着重复次数无限增加，其soundness error将趋近于1。
- 这种并行重复“failure”是常见的：
- 如常发生于大量PCPs for NP-complete languages。
- 提供并行重复的变种——CPR（consistent parallel repetition），具有与普通并行重复 相同的随机值复杂度和query复杂度。
- CPR会让每个（具有non-trivial soundness error的）PCP的soundness error为0。
本文通过提供a characterization result，对这种意外现象进行了解释：
- 当前仅当PCP的特定“MIP projection”的soundness error严格小于1，该PCP的并行重复才能让其soundness error为0。
这篇关于PCP的Parallel Repetition的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
