Lorenzo Ciardo
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
Ciardo, Lorenzo; Kozik, Marcin; Krokhin, Andrei; Nakajima, Tamio-Vesa; Živný, Stanislav
Authors
Marcin Kozik
Professor Andrei Krokhin andrei.krokhin@durham.ac.uk
Professor
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
Published Journal Article
(790 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
You might also like
Topology and adjunction in promise constraint satisfaction
(2023)
Journal Article
Algebraic Approach to Promise Constraint Satisfaction
(2021)
Journal Article
Robust algorithms with polynomial loss for near-unanimity CSPs
(2019)
Journal Article
Towards a characterization of constant-factor approximable Finite-Valued CSPs
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search