Journal article
1-in-3 vs. not-all-equal: dichotomy of a broken promise
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 1.1MB, Terms of use)
-
- Publisher copy:
- 10.1145/3719007
Authors
+ National Science Centre
More from this funder
- Funder identifier:
- https://ror.org/03ha2q922
- Grant:
- 2021/03/Y/ST6/00171
- Programme:
- Weave-UNISONO
+ UK Research and Innovation
More from this funder
- Funder identifier:
- https://ror.org/001aqnf71
- Grant:
- EP/X024431/1
+ Engineering and Physical Sciences Research Council
More from this funder
- Funder identifier:
- https://ror.org/0439y7842
- Grant:
- EP/X033201/1
- Publisher:
- Association for Computing Machinery
- Journal:
- ACM Transactions on Computational Logic More from this journal
- Volume:
- 26
- Issue:
- 2
- Article number:
- 10
- Publication date:
- 2025-04-23
- Acceptance date:
- 2025-02-14
- DOI:
- EISSN:
-
1557-945X
- ISSN:
-
1529-3785
- Language:
-
English
- Keywords:
- Pubs id:
-
2086231
- Local pid:
-
pubs:2086231
- Deposit date:
-
2025-02-15
Terms of use
- Copyright holder:
- Ciardo et al.
- Copyright date:
- 2025
- Rights statement:
- © 2025 Copyright held by the owner/author(s). This work is licensed under Creative Commons Attribution International 4.0.
- Notes:
- This research was funded in whole or in part by UK Research and Innovation (EP/X024431/1). For the purpose of Open Access, the authors have applied a Creative Commons Attribution (CC BY) license to any Accepted Manuscript version arising. All data is provided in full in the results section of this paper.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record