The complexity of promise SAT on non-Boolean domains

Abstract

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 $\frac{g}{k}<\frac{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.

Full version of an ICALP 2020 paper

References in corpus (1)

• The complexity of 3-colouring $H$-colourable graphs

Cited by in corpus (11)

• CLAP: A New Algorithm for Promise CSPs
• Local consistency as a reduction between constraint satisfaction problems
• An invitation to the promise constraint satisfaction problem
• Linearly ordered colourings of hypergraphs
• Beyond PCSP (1-in-3,NAE)
• Topology and adjunction in promise constraint satisfaction
• On the complexity of symmetric vs. functional PCSPs
• Approximate Graph Colouring and the Crystal with a Hollow Shadow
• Injective hardness condition for PCSPs
• Hierarchies of Minion Tests for PCSPs through Tensors
• 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise