Which NP-Hard SAT and CSP Problems Admit Exponentially Improved Algorithms?
share
We study the complexity of SAT(Γ) problems for potentially infinite languages Γ closed under variable negation (sign-symmetric languages). Via an algebraic connection, this reduces to the study of restricted partial polymorphisms of Γ we refer to as pSDI-operations (for partial, self-dual and idempotent). First, we study the language classes themselves. We classify the structure of the least restrictive pSDI-operations, corresponding to the most powerful languages Γ, and find that these operations can be divided into levels, corresponding to a rough notion of difficulty; and that within each level there is a strongest operation (the partial k-NU operation, preserving (k-1)-SAT) and a weakest operation (the k-universal operation u_k, preserving problems definable via bounded-degree polynomials). We show that every sign-symmetric Γ not preserved by u_k implements all k-clauses; thus if Γ is not preserved by u_k for any k, then SAT(Γ) is trivially SETH-hard and cannot be solved faster than O^*(2^n) unless SETH fails. Second, we study upper and lower bounds for SAT(Γ) for such languages. We show that several classes in the hierarchy correspond to problems which can be solved faster than 2^n using previously known algorithmic strategies such as Subset Sum-style meet-in-the-middle and fast matrix multiplication. Furthermore, if the sunflower conjecture holds for sunflowers with k sets, then the partial k-NU language has an improved algorithm via local search. Complementing this, we show that for every class there is a concrete lower bound c such that SAT(Γ) cannot be solved faster than O^*(c^n) for all problems in the class unless SETH fails. This gives the first known case of a SAT-problem which simultaneously has non-trivial upper and lower bounds under SETH.
READ FULL TEXT