The complexity of promise SAT on non-Boolean domains

DOI10.1145/3470867MaRDI QIDQ5066145zbMATH OpenOpenAlexWikidataFDO

Authors Alex Brandts, Marcin Wrochna, S. Zivny

Publication date 29 March 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.09065

zbMATH Keywords

algebraic approachlabel coverPCSPpolymorphismspromise constraint satisfaction

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07)

Abstract: While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin, Guruswami, and H {a}stad roved a result known as "$(2+varepsilon)$-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 $fracgk<frac12$ 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.

Recommendations

• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• (2+)-Sat is NP-hard
• The Nonapproximability of Non-Boolean Predicates
• Algebraic Approach to Promise Constraint Satisfaction

Cited in

(16)

• Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Algebraic approach to promise constraint satisfaction
• (2+)-Sat is NP-hard
• CLAP: A New Algorithm for Promise CSPs
• Topology and Adjunction in Promise Constraint Satisfaction
• SDPs and robust satisfiability of promise CSP
• Approximate graph colouring and the hollow shadow
• Approximate graph coloring and the crystal with a hollow shadow
• Local consistency as a reduction between constraint satisfaction problems
• 1-in-3 vs. not-all-equal: dichotomy of a broken promise
• Injective hardness condition for PCSPs
• 1-in-3 vs. not-all-equal: dichotomy of a broken promise
• Linearly ordered colourings of hypergraphs
• On the complexity of symmetric vs. functional PCSPs

This page was built for publication: The complexity of promise SAT on non-Boolean domains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066145)