The complexity of promise SAT on non-Boolean domains

Alex Brandts, Marcin Wrochna, Stanislav Živný

While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin, Guruswami, and Håstad roved a result known as "$(2+\epsilon )$-SAT is NP-hard" [FOCS'14/SICOMP'17]. They sh…