Name
Abstract | ||
|---|---|---|
Abstract For several NP-complete problems, there have been a progression of better but still exp onential algorithms. In this paper, we address the relative likelihood of sub-exponential algorithmsfor these problems. We introduce a generalized reduction which we call Sub-Exponential Reduction Family (SERF) that preserves sub-exponential complexity. We show that Circuit- SAT is SERF-complete for allNP-search problems, and that for any fixed , -SAT, -Colorability, -Set Cover, Independent Set, Clique, 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 bo unds for AC ; that is, bounds of the form . This problem is even open for depth-3 circuits. In fact, such a bound for dept h-3 circuits with even limited (at most ) fan-in for bottom-level gates would imply a nonlinear size lower bound,fo r logarithmic depth circuits. We show that with high probability even degree 2 random GF(2) polynomials require stron gly exponential size for circuits for,. We thus exhibit a much smaller space of,functions such that almost every function in this class requires str ongly exponential size circuits. As a corollary, we derive a pseudorandom generator (requiri ng bits of advice) that maps bits into a larger number,of bits so that computing,parity on the r ange is hard for,circuits. Our main technical lemma is an algorithm that, for any fixed , represents an arbitrary -CNF formula as a disjunc- tion of -CNF formulas that aresparse, that is, each has clauses. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1006/jcss.2001.1774 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
exponential complexity,second order,lower bound,np complete problem,first order,set cover,independent set,np complete problems,vertex cover,circuits,computational geometry,polynomials,writing,computational complexity | Conference | 63 |
Issue | ISSN | ISBN |
4 | 0022-0000 | 0-8186-9172-7 |
Citations | PageRank | References |
304 | 10.75 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Russell Impagliazzo | 1 | 5444 | 482.13 |
| Ramamohan Paturi | 2 | 1260 | 92.20 |
| Francis Zane | 3 | 610 | 42.52 |