Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
Andrei Krokhin, Danny Vagnozzi
Given a satisfiable instance of 1-in-3 SAT, it is NP-hard to find a satisfying assignment for it, but it may be possible to efficiently find a solution subject to a weaker (not nec…
cs.CC2025
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin +2
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…