标题： 基于PCPP的重新配置不可近似性：查询复杂性与可靠性间隙的权衡 显示英文标题

标题： PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs

摘要： 重新配置不可逼近性假设（RIH），最近由Hirahara-Ohsaka（STOC'24）和Karthik-Manurangsi（ECCC'24）建立，研究了在限制为近似中间解的情况下，在约束满足问题（CSP）中将一个解重新配置为另一个解的难度。 在这项工作中，我们建立了RIH的可靠性间隙与可概率检查接近证明（PCPP）的可靠性间隙之间更紧密的联系。 因此，我们在Gap CSP重新配置中实现了可靠性与查询复杂性之间更好的权衡。 我们的方法利用了一个并行化框架，该框架也出现在一些最近的参数化不可逼近性结果中。 显示英文摘要

摘要： The Reconfiguration Inapproximability Hypothesis (RIH), recently established by Hirahara-Ohsaka (STOC'24) and Karthik-Manurangsi (ECCC'24), studies the hardness of reconfiguring one solution into another in constraint satisfaction problems (CSP) when restricted to approximate intermediate solutions. In this work, we make a tighter connection between RIH's soundness gap and that of probabilistically checkable proofs of proximity (PCPP). Consequently, we achieve an improved trade-off between soundness and query complexity in Gap CSP Reconfiguration. Our approach leverages a parallelization framework, which also appears in some recent parameterized inapproximability results.