UC San Diego

The exponential complexity of a parameterized problem P is the infimum of those c such that P can be solved in time poly(IxI)2cn on inputs x of parameter n. For example, any (d, k)-constraint satisfaction problem over n variables can be solved in time poly(IxI-dn, and so has exponential complexity at most lg d. We thoroughly explore the exponential complexity of k-SAT. We - show that the exponential complexities of k-SAT and SAT with clause density or frequency [Delta] are approximately the same when lg Delta] is between [Omega](k) and O(k lg k) - upper bound the gap between the exponential complexities of k- SAT and Unique-k-SAT by [Omega](lg² k/k), and show that this is nearly optimal for current techniques. For the non -promise version of Unique-k-SAT, we reduce this gap to 0. - lower bound the exponential complexity of [pi]₂ 3-SAT, a canonical problem at the 2nd level of the polynomial hierarchy, by that of k-SAT, independent of k, showing that a major technical hurdle must be jumped to construct nontrivial algorithms for this problem. - give what is likely the first nontrivial algorithm for the satisfiability of circuits of constant depth and linear size