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
|