2026-07-22T06:11:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26572 2026-07-01T07:16:15Z ddc:004 open_access

Approximating 1-In-3 SAT by Linearly Ordered Hypergraph 3-Colouring Is NP-Hard Krokhin, Andrei Vagnozzi, Danny Constraint satisfaction complexity theory 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrei Krokhin and Danny Vagnozzi 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.184 urn:nbn:de:0030-drops-265729 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.184 eng https://creativecommons.org/licenses/by/4.0/legalcode