一句话：建立框架在 promise CSP 与无限域 CSP 间转移结果，给出新的 NP 难判定及时间约束多项式算法。
本文研究 promise 约束满足问题（promise CSP）与无限域 CSP 之间的联系。作者建立了一个代数与算法框架，使结果能在两类问题之间双向转移：一方面用于无限域 CSP，得到新的代数判据和 NP 难性准则；另一方面构造出有限模板的 promise CSP，它们可归约到 Bodirsky-Pinsker 猜想范围内的可 tractable 无限域 CSP，却不是有限 tractable，从而揭示两领域的非平凡联系。证明的关键部分还给出了求解时间约束满足问题的一致多项式时间算法。
We establish a framework that allows us to transfer results between some constraint satisfaction problems with infinite templates and promise constraint satisfaction problems. On the one hand, we obtain new algebraic results for infinite-domain CSPs giving new criteria for NP-hardness. On the other hand, we show the existence of promise CSPs with finite templates that reduce naturally to tractable infinite-domain CSPs in the scope of the Bodirsky-Pinsker conjecture, but that are not finitely tractable, thereby showing a non-trivial connection between those two fields of research. In an important part of our proof, we also obtain uniform polynomial-time algorithms solving temporal constraint satisfaction problems.
DOI 原文 ·
@inproceedings{paperbot8636,
title = {Algebraic and algorithmic synergies between promise and infinite-domain CSPs},
author = {Antoine Mottet},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00034}
}