Discrete mathematics

Complexity class

Time complexity

Upper and lower bounds

Mathematics

Exponential function

Mathematical analysis

Combinatorics

Journal of Computer and System Sciences

For several NP -complete problems, there have been a progression of better but still exponential algorithms. In this paper, we address the relative likelihood of sub-exponential algorithms for these problems. We introduce a generalized reduction that we call Sub-exponential Reduction Family (SERF) that preserves sub-exponential complexity. We show that Circuit-SAT is SERF-complete for all NP -search problems, and that for any fixed k ⩾3, k -SAT, k -Colorability, k -Set Cover, Independent Set, Clique, and Vertex Cover, are SERF-complete for the class SNP of search problems expressible by second-order existential formulas whose first-order part is universal. In particular, sub-exponential complexity for any one of the above problems implies the same for all others. We also look at the issue of proving strongly exponential lower bounds for AC 0 , that is, bounds of the form 2 Ω ( n ) . This problem is even open for depth-3 circuits. In fact, such a bound for depth-3 circuits with even limited (at most n ε ) fan-in for bottom-level gates would imply a nonlinear size lower bound for logarithmic depth circuits. We show that with high probability even random degree 2 GF (2) polynomials require strongly exponential size for Σ k 3 circuits for k = o (log log n ). We thus exhibit a much smaller space of 2 O ( n 2 ) functions such that almost every function in this class requires strongly exponential size Σ k 3 circuits. As a corollary, we derive a pseudorandom generator (requiring O ( n 2 ) bits of advice) that maps n bits into a larger number of bits so that computing parity on the range is hard for Σ k 3 circuits. Our main technical lemma is an algorithm that, for any fixed ε >0, represents an arbitrary k -CNF formula as a disjunction of 2 εn k -CNF formulas that are sparse, that is, each disjunct has O ( n ) clauses.

Which Problems Have Strongly Exponential Complexity?