Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

The Complexity of Promise SAT on Non-Boolean Domains

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:18:34Z
dc.abstract.enWhile 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
dc.affiliationUniwersytet Warszawski
dc.contributor.authorWrochna, Marcin
dc.contributor.authorBrandts, Alex
dc.contributor.authorŽivný, Stanislav
dc.date.accessioned2024-01-26T10:09:21Z
dc.date.available2024-01-26T10:09:21Z
dc.date.issued2021
dc.description.financePublikacja bezkosztowa
dc.description.number4
dc.description.volume13
dc.identifier.doi10.1145/3470867
dc.identifier.issn1942-3454
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/122014
dc.identifier.weblinkhttp://www.scopus.com/inward/record.url?eid=2-s2.0-85114289728&partnerID=MN8TOARS
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofACM Transactions on Computation Theory
dc.relation.pages1-20
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleThe Complexity of Promise SAT on Non-Boolean Domains
dc.typeJournalArticle
dspace.entity.typePublication