Can I read 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise on EtoBox?

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise by Ciardo, Lorenzo; Kozik, Marcin; Krokhin, Andrei; Nakajima, Tamio-Vesa; Živný, Stanislav is a scholarly article available to read on EtoBox.

What is 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise about?

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.

Author

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

Published

2023

Language

EN