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.

We compare the capabilities of two approaches to approximating graph isomorphism using linear algebraic methods: the invertible map tests (introduced by Dawar and Holm) and proof systems with algebraic rules, namely polynomial calculus, monomial calculus and Nullstellensatz calculus. In the case of fields of characteristic zero, these variants are all essentially equivalent to the Weisfeiler-Leman algorithms. In positive characteristic we show that the distinguishing power of the monomial calculus is no greater than the invertible map method by simulating the former in a fixed-point logic with solvability operators. In turn, we show that the distinctions made by this logic can be implemented in the Nullstellensatz calculus.