Regular Article
Which Problems Have Strongly Exponential Complexity?

https://doi.org/10.1006/jcss.2001.1774Get rights and content
Under an Elsevier user license
open archive

Abstract

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 AC0, 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 Σk3 circuits for k=o(log log n). We thus exhibit a much smaller space of 2O(n2) functions such that almost every function in this class requires strongly exponential size Σk3 circuits. As a corollary, we derive a pseudorandom generator (requiring O(n2) bits of advice) that maps n bits into a larger number of bits so that computing parity on the range is hard for Σk3 circuits. Our main technical lemma is an algorithm that, for any fixed ε>0, represents an arbitrary k-CNF formula as a disjunction of 2εnk-CNF formulas that are sparse, that is, each disjunct has O(n) clauses.

Cited by (0)

This research material is based upon work supported by NSF Grants CCR-9734911 and CCR-0098197 from the Theory of Computing Program as well as by the grant #93025 of the joint US-Checkoslovakia Science and Technology Program.