The exponential complexity of satisfiability problems.

摘要

The exponential complexity of a parameterized problem P is the infimum of those c such that P can be solved in time poly(|x|)2cn on inputs x of parameter n. For example, any (d, k)-constraint satisfaction problem over n variables can be solved in time poly(|x|) dn, and so has exponential complexity at most lg d. We thoroughly explore the exponential complexity of k -SAT. We (1) 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 O(k) and O(k lg k). (2) upper bound the gap between the exponential complexities of k-SAT and Unique- k-SAT by O&parl0;lg2kk&parr0; , 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. (3) lower bound the exponential complexity of pi2 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. (4) give what is likely the first nontrivial algorithm for the satisfiability of circuits of constant depth and linear size.