Approximating 1-In-3 SAT by Linearly Ordered Hypergraph 3-Colouring Is NP-Hard
Andrei Krokhin, Danny Vagnozzi · arXiv (Cornell University) · 2025
1-in-3 SAT is a classical NP-hard constraint satisfaction problem (CSP). 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 necessarily Boolean) predicate than "1-in-3". There is a conjecture, which we call the Approximate 1-in-3 SAT conjecture, made independently by several researchers, that predicts a dichotomy: for certain choices of weaker predicates the problem becomes tractable and for the remaining choices the task remains NP-hard. Such problems belong to the Promise CSP (PCSP) framework, which studies how one CSP can be approximated by another, in a specific qualitative sense. The Approximate 1-in-3 SAT conjecture is notable because there is no P versus NP-hard dichotomy conjecture for general PCSPs yet (due to insufficient evidence). One specific predicate, corresponding to the problem of linearly ordered 3-colouring of 3-uniform hypergraphs, has been mentioned in several recent papers as an obstacle to further progress in proving the Approximate 1-in-3 SAT conjecture. We prove that the problem for this predicate is NP-hard, as predicted by the conjecture. This completes the proof of the conjecture for predicates on a 3-element domain.