While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin, Guruswami, and Håstad roved a result known as “\((2+\epsilon)\)-SAT is NP-hard” [FOCS’14/SICOMP’17]. They showed that the problem of distinguishing \(k\)-CNF formulas that are \(g\)-satisfiable (i.e. some assignment satisfies at least \(g\) literals in every clause) from those that are not even 1-satisfiable is NP-hard if \(g / k < 1 / 2\) and is in P otherwise. We study a generalisation of SAT on arbitrary finite domains, with clauses that are disjunctions of unary constraints, and establish analogous behaviour. Thus we give a dichotomy for a natural fragment of promise constraint satisfaction problems (PCSPs) on arbitrary finite domains.
The hardness side is proved using the algebraic approach, via a new general NP-hardness criterion on polymorphisms of the problem, based on a gap version of the Layered Label Cover problem. We show that previously used criteria are insufficient – the problem hence gives an interesting benchmark of algebraic techniques for proving hardness of approximation problems such as PCSPs.