The complexity of promise SAT on non-Boolean domains
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 a...
| Главные авторы: | , , |
|---|---|
| Формат: | Conference item |
| Язык: | English |
| Опубликовано: |
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
2020
|
| _version_ | 1826268127483133952 |
|---|---|
| author | Brandts, A Wrochna, M Živný, S |
| author_facet | Brandts, A Wrochna, M Živný, S |
| author_sort | Brandts, A |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T21:04:50Z |
| format | Conference item |
| id | oxford-uuid:3c178cb7-5b45-4964-8007-066edba89d99 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T21:04:50Z |
| publishDate | 2020 |
| publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| record_format | dspace |
| spelling | oxford-uuid:3c178cb7-5b45-4964-8007-066edba89d992022-03-26T14:11:31ZThe complexity of promise SAT on non-Boolean domainsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:3c178cb7-5b45-4964-8007-066edba89d99EnglishSymplectic ElementsSchloss Dagstuhl - Leibniz-Zentrum für Informatik2020Brandts, AWrochna, MŽivný, SWhile 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. |
| spellingShingle | Brandts, A Wrochna, M Živný, S The complexity of promise SAT on non-Boolean domains |
| title | The complexity of promise SAT on non-Boolean domains |
| title_full | The complexity of promise SAT on non-Boolean domains |
| title_fullStr | The complexity of promise SAT on non-Boolean domains |
| title_full_unstemmed | The complexity of promise SAT on non-Boolean domains |
| title_short | The complexity of promise SAT on non-Boolean domains |
| title_sort | complexity of promise sat on non boolean domains |
| work_keys_str_mv | AT brandtsa thecomplexityofpromisesatonnonbooleandomains AT wrochnam thecomplexityofpromisesatonnonbooleandomains AT zivnys thecomplexityofpromisesatonnonbooleandomains AT brandtsa complexityofpromisesatonnonbooleandomains AT wrochnam complexityofpromisesatonnonbooleandomains AT zivnys complexityofpromisesatonnonbooleandomains |