2026-07-26T16:58:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12424 2024-03-06T10:50:06Z ddc:004 open_access

The Complexity of Promise SAT on Non-Boolean Domains Brandts, Alex Wrochna, Marcin Živný, Stanislav promise constraint satisfaction PCSP polymorphisms algebraic approach label cover While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin, Guruswami, and Håstad [FOCS'14/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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alex Brandts and Marcin Wrochna and Stanislav Živný 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.17 urn:nbn:de:0030-drops-124241 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.17 eng https://creativecommons.org/licenses/by/3.0/legalcode