Skip to main content

Research Repository

Advanced Search

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

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

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


Authors

Lorenzo Ciardo

Marcin Kozik

Tamio-Vesa Nakajima

Stanislav Živný



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. (2024, July). 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. Presented at LLICS '24: 39th Annual ACM/IEEE Symposium on Logic in Computer Science, Tallinn, Estonia

Presentation Conference Type Conference Paper (published)
Conference Name LLICS '24: 39th Annual ACM/IEEE Symposium on Logic in Computer Science
Start Date Jul 8, 2024
End Date Jul 11, 2024
Acceptance Date Feb 14, 2025
Online Publication Date Jul 8, 2024
Publication Date Jul 8, 2024
Deposit Date Oct 1, 2024
Publicly Available Date Oct 2, 2024
Journal ACM Transactions on Computational Logic
Print ISSN 1529-3785
Electronic ISSN 1557-945X
Peer Reviewed Peer Reviewed
Volume 24
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
Other Repo URL https://arxiv.org/abs/2302.03456

Files





You might also like



Downloadable Citations