The Complexity of Promise SAT on Non-Boolean Domains
Alex Brandts, Marcin Wrochna, Stanislav Živný
Abstract
While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin et al. [SICOMP’17] proved a result known as “(2+ɛ)-SAT is NP-hard.” 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, which is 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 in problems such as PCSPs.