Skip to main content
eScholarship
Open Access Publications from the University of California

UC San Diego

UC San Diego Electronic Theses and Dissertations bannerUC San Diego

The exponential complexity of satisfiability problems

  • Author(s): Calabro, Chris
  • et al.
Abstract

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

Main Content
Current View