Conference item icon

Conference item

The complexity of promise SAT on non-Boolean domains

Alternative title:
Conference paper
Abstract:

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 disjunc...

Expand abstract
Publication status:
Published
Peer review status:
Reviewed (other)

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.ICALP.2020.17
Publication website:
https://drops.dagstuhl.de/opus/volltexte/2020/12424/

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
ORCID:
0000-0001-9346-2172
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik Publisher's website
Journal:
Leibniz International Proceedings in Informatics Journal website
Volume:
168
Article number:
17
Publication date:
2020-06-29
Acceptance date:
2020-04-15
Event title:
ICALP
Event location:
Saarbrücken, Germany
Event website:
https://icalp2020.saarland-informatics-campus.de/
Event start date:
2020-07-08T00:00:00Z
Event end date:
2020-07-11T00:00:00Z
DOI:
ISSN:
1868-8969
ISBN:
9783959771382
Language:
English
Keywords:
Pubs id:
1100413
Local pid:
pubs:1100413
Deposit date:
2020-04-16

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP