The complexity of promise SAT on non-Boolean domains
While 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 th...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for Computing Machinery
2021
|