1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise

Ciardo, Lorenzo; Kozik, Marcin; Krokhin, Andrei; Nakajima, Tamio-Vesa; Živný, Stanislav

Abstract

The 1-in-3 and Not-All-Equal satisfiability problems for Boolean CNF formulas are two well-known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Equal 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.

Citation

Ciardo, L., Kozik, M., Krokhin, A., Nakajima, T.-V., & Živný, S. (online). 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. ACM Transactions on Computational Logic, https://doi.org/10.1145/3719007

• Journal Article Type: Article
• Acceptance Date: Feb 20, 2025
• Online Publication Date: Feb 20, 2025
• Deposit Date: Feb 26, 2025
• Publicly Available Date: Feb 27, 2025
• Journal: ACM Transactions on Computational Logic
• Print ISSN: 1529-3785
• Electronic ISSN: 1557-945X
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• DOI: https://doi.org/10.1145/3719007
• Public URL: https://durham-repository.worktribe.com/output/3548339
• Other Repo URL: https://arxiv.org/abs/2302.03456