期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-13
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We revisit one original motivation for the study of no-signaling multi-prover interactive proofs (NSMIPs): specifically, that two spatially separated provers are guaranteed to be no-signaling by the physical principle that information cannot travel from one point to another faster than light. We observe that with more than two provers, the physical connection between no-signaling and faster-than-light communication is more nuanced, depending on the relative positioning of the provers. In particular, we observe that provers are guaranteed to be no-signaling if and only if their positions are convexly independent. Other prover positionings provide weaker guaranteees. We consider a new issue that thus arises only in the many-prover setting: how precisely must provers be positioned in order to guarantee the soundness of a (NS-)MIP? We prove that substantially more precision is required to guarantee full no-signaling than to guarantee soundness of a specific NS-MIP for PSPACE implicit in the work of Kalai and Raz (CRYPTO 2009).
