证明了承诺CSP的搜索问题难以求解，且相关元问题不可判定。
Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
- 基于代数方法，揭示主流算法在搜索问题上无效
- 证明搜索解的构造等价于TFNP类中最难问题
- 发现多个与多项式相关的元问题不可判定
承诺约束满足问题（PCSP）的搜索与决策版本是否等价仍是开放问题。现有主流算法（BLP、AIP、BLP+AIP）仅解决决策问题，其解的舍入转化为搜索证书的过程可能等价于任意TFNP问题，即本质上无法有效求解搜索问题。通过代数框架，本文给出充分条件以证明此类算法对搜索无效，并扩展至元问题：基于特定极小子结构表征的算法家族所对应的模板集合不可判定。进一步地，分析已知可保证有限模板CSP可解性的代数条件，证明关于循环同态和弱凝聚多项式的多个元问题在PCSP中同样不可判定。特别地，不存在算法能判断一个有限模板的PCSP是否具有循环同态或弱凝聚多项式。
原文摘要 · Abstract (English)
It is an open question whether the search and decision versions of promise CSPs are equivalent. Most known algorithms for PCSPs solve only their \emph{decision} variant, and it is unknown whether they can be adapted to solve \emph{search} as well. The main approaches, called BLP, AIP and BLP+AIP, handle a PCSP by finding a solution to a relaxation of some integer program. We prove that rounding those solutions to a proper search certificate can be as hard as any problem in the class TFNP. In other words, these algorithms are ineffective for search. Building on the algebraic approach to PCSPs, we find sufficient conditions that imply ineffectiveness for search. Our tools are tailored to algorithms that are characterized by minions in a suitable way, and can also be used to prove undecidability results for meta-problems. This way, we show that the families of templates solvable via BLP, AIP, and BLP+AIP are undecidable. Using the same techniques we also analyze several algebraic conditions that are known to guarantee the tractability of finite-template CSPs. We prove that several meta-problems related to cyclic polymorphims and WNUs are undecidable for PCSPs. In particular, there is no algorithm deciding whether a finite PCSP template (1) admits cyclic a polymorphism, (2) admits a WNU.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。