IP = PSPACE Using Error-Correcting Codes
IP = PSPACE Using Error-Correcting Codes
复制标题
IP = PSPACE 使用纠错码
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Or Meir
中科院分区：
文献类型：
--
作者：
Or Meir
$\mathbf{IP}$ 定理，断言 $\mathbf{IP}=\mathbf{PSPACE}$ [Lund et al., J. ACM, 39 (1992), pp. 859--868; Shamir, J. ACM, 39 (1992), pp. 878--880]，是复杂性理论的主要成就之一。该定理的已知证明基于算术化技术，该技术将量化的布尔公式转换为相关的多项式。多项式的使用背后的直觉通常可以通过多项式构成良好的纠错码这一事实来解释。然而，已知的证明似乎是针对多项式的使用而定制的，并且不能推广到任意纠错码。在这项工作中，我们证明 $\mathbf{IP}$ 定理可以通过使用通用纠错码及其张量积来证明。我们相信，这为上述直觉奠定了严格的基础，并进一步阐明了 $\mathbf{IP}$ 定理。
The $\mathbf{IP}$ Theorem, which asserts that $\mathbf{IP}=\mathbf{PSPACE}$ [Lund et al., J. ACM, 39 (1992), pp. 859--868; Shamir, J. ACM, 39 (1992), pp. 878--880], is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a quantified Boolean formula into a related polynomial. The intuition that underlies the use of polynomials is commonly explained by the fact that polynomials constitute good error-correcting codes. However, the known proofs seem tailored to the use of polynomials and do not generalize to arbitrary error-correcting codes. In this work, we show that the $\mathbf{IP}$ theorem can be proved by using general error-correcting codes and their tensor products. We believe that this establishes a rigorous basis for the aforementioned intuition and sheds further light on the $\mathbf{IP}$ theorem.