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

February 07, 2023 ยท The Ethereal ยท ๐Ÿ› ACM Transactions on Computational Logic

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin, Tamio-Vesa Nakajima, Stanislav ลฝivnรฝ arXiv ID 2302.03456 Category cs.CC: Computational Complexity Cross-listed cs.DM, cs.DS Citations 1 Venue ACM Transactions on Computational Logic Last Checked 2 months ago
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.
Community shame:
Not yet rated
๐Ÿ“„ View on arXiv ๐ŸŒ View on ar5iv ๐Ÿ“‘ PDF ๐ŸŽ‰ Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Computational Complexity