标题： 间隙保持归约和独立集博弈的RE完全性 显示英文标题

标题： Gap-preserving reductions and RE-completeness of independent set games

摘要： 在复杂性理论中，保持间隙的归约在研究近似难度和分析多证明者交互式证明系统的相对复杂性中起着关键作用。 在量子设置中，具有纠缠证明者的多证明者交互式证明系统对应于非局部游戏的带间隙的承诺问题，最近的结果 MIP$^*$=RE \cite{ji2020mipre}表明这些问题是通常不可判定的。 然而，MIP$^*$内部问题的相对复杂性仍然没有被很好地理解，因为在量子设置中建立保持间隙的归约带来了新的挑战。 在本文中，我们引入了一个框架来研究此类归约，并利用它来确立独立集游戏的带间隙承诺问题的 MIP$^*$完全性。 在这样的游戏中，目标是确定给定图是否包含指定大小的独立集。 我们构造了具有常数问题大小的独立集游戏族，其中带间隙的承诺问题是不可判定的。 相反，在经典设置中，同一问题可以在多项式时间内判定。 为了进行我们的归约，我们建立了一个新的稳定性定理，这可能具有独立的兴趣，使我们能够将几乎 PVMs 的族扰动为真正的 PVMs。 显示英文摘要

摘要： In complexity theory, gap-preserving reductions play a crucial role in studying hardness of approximation and in analyzing the relative complexity of multiprover interactive proof systems. In the quantum setting, multiprover interactive proof systems with entangled provers correspond to gapped promise problems for nonlocal games, and the recent result MIP$^*$=RE \cite{ji2020mipre} shows that these are in general undecidable. However, the relative complexity of problems within MIP$^*$ is still not well-understood, as establishing gap-preserving reductions in the quantum setting presents new challenges. In this paper, we introduce a framework to study such reductions and use it to establish MIP$^*$-completeness of the gapped promise problem for the natural class of independent set games. In such a game, the goal is to determine whether a given graph contains an independent set of a specified size. We construct families of independent set games with constant question size for which the gapped promise problem is undecidable. In contrast, the same problem is decidable in polynomial time in the classical setting. To carry out our reduction, we establish a new stability theorem, which could be of independent interest, allowing us to perturb families of almost PVMs to genuine PVMs.