论文标题
邀请承诺限制满意度问题
An invitation to the promise constraint satisfaction problem
论文作者
论文摘要
在过去的二十年中，以Feder-Vardi二分法猜想为中心的约束满意度问题（CSP）的复杂性研究非常突出。经过漫长的努力和许多部分结果，二分法猜想在2017年由Bulatov和Zhuk独立证明。大约同时，CSP的广泛概括（称为Promise CSP）已开始获得突出。在这项调查中，我们解释了Promise CSP的重要性，并强调了对CSP研究的许多新的非常有趣的功能。对Promis CSP的复杂性分类寻求是广泛的，我们认为，尽管承诺CSP更一般，但与CSP的二分法领导的研究相比，广泛的研究人员更容易获得此任务。
The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and Zhuk. At about the same time, a vast generalisation of CSP, called promise CSP, has started to gain prominence. In this survey, we explain the importance of promise CSP and highlight many new very interesting features that the study of promise CSP has brought to light. The complexity classification quest for the promise CSP is wide open, and we argue that, despite the promise CSP being more general, this quest is rather more accessible to a wide range of researchers than the dichotomy-led study of the CSP has been.
