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-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.

Citation

Ciardo, L., Kozik, M., Krokhin, A., Nakajima, T.-V., & Živný, S. (2024, July). 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. Presented at LICS '24: 39th Annual ACM/IEEE Symposium on Logic in Computer Science, Tallinn Estonia

• Presentation Conference Type: Conference Paper (published)
• Conference Name: LICS '24: 39th Annual ACM/IEEE Symposium on Logic in Computer Science
• Start Date: Jul 8, 2024
• End Date: Jul 11, 2024
• Acceptance Date: Apr 15, 2024
• Online Publication Date: Jul 8, 2024
• Publication Date: Jul 8, 2024
• Deposit Date: Oct 1, 2024
• Publicly Available Date: Oct 2, 2024
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Pages: 1-12
• Book Title: LICS '24: Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science
• ISBN: 9798400706608
• DOI: https://doi.org/10.1145/3661814.3662069
• Public URL: https://durham-repository.worktribe.com/output/2925337
• Additional Information: Published: 2024-07-08