一句话：研究 promise 被 rainbow-free 结构从任一侧削弱后的 1-in-3/Not-All-Equal CSP，并建立复杂度二分性。
布尔 CNF 上的 1-in-3 可满足性与 Not-All-Equal 可满足性均为著名的 NP 难问题；但二者之间的 promise 版本（promise 1-in-3 vs. Not-All-Equal）却可在多项式时间内求解。本文研究该约束满足问题的一类变体：从任一侧用 rainbow-free 结构削弱原有的 promise，从而得到一族新的计算问题。作者在此设定下建立了复杂度二分定理，即对该类中的每个问题判定其为多项式时间可解或 NP 难。这一结果刻画了 promise 被部分破坏后 1-in-3 与 Not-All-Equal 之间 CSP 的复杂度边界。
The 1-in-3 and Not-All-Eqal satisfiability problems for Boolean CNF formulas are two well-known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Eqal problem can be solved in polynomial time. In the present work, we investigate this constraint satisfaction problem in a regime where the promise is weakened from either side by a rainbow-free structure, and establish a complexity dichotomy for the resulting class of computational problems.
@inproceedings{CiardoKKNZ24,
title = {1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise},
author = {Lorenzo Ciardo and Marcin Kozik and Andrei Krokhin and Tamio-Vesa Nakajima and Stanislav Živný},
booktitle = {LICS},
year = {2024},
doi = {10.1145/3661814.3662069}
}