Which problems have strongly exponential complexity?

*(English)*Zbl 1006.68052Summary: 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 algorithm 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\geq 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^{\Omega(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^\varepsilon\)) 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 \(\Sigma^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 \(\Sigma^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 \(\Sigma^k_3\) circuits. Our main technical lemma is an algorithm that, for any fixed \(\varepsilon> 0\), represents an arbitrary \(k\)-CNF formula as a disjunction of \(2^{\varepsilon n}\) \(k\)-CNF formulas that are sparse, that is, each disjunct has \(O(n)\) clauses.

We also look at the issue of proving strongly exponential lower bounds for AC\(^0\), that is, bounds of the form \(2^{\Omega(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^\varepsilon\)) 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 \(\Sigma^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 \(\Sigma^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 \(\Sigma^k_3\) circuits. Our main technical lemma is an algorithm that, for any fixed \(\varepsilon> 0\), represents an arbitrary \(k\)-CNF formula as a disjunction of \(2^{\varepsilon n}\) \(k\)-CNF formulas that are sparse, that is, each disjunct has \(O(n)\) clauses.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |

PDF
BibTeX
XML
Cite

\textit{R. Impagliazzo} et al., J. Comput. Syst. Sci. 63, No. 4, 512--530 (2001; Zbl 1006.68052)

Full Text:
DOI

##### References:

[1] | Abrahamson, K.A.; Downe, R.G.; Fellows, M.R., Fixed parameter tractability and completeness IV: on completeness for W[P] and PSPACE analogues, Annals of pure applied logic, (1995), p. 235-276 · Zbl 0828.68077 |

[2] | Ajtái, M., σ11-formulae on finite structures, Ann. pure appl. logic, 24, 1-48, (1983) · Zbl 0519.03021 |

[3] | Alon, N.; Spencer, J.; Erdős, P., The probabilistic method, (1992), Wiley New York |

[4] | Arora, S., Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proc. 37th IEEE symposium on foundations of computer science (FOCS), (1996), p. 2-11 |

[5] | Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szeged, M., Proof verification and hardness of approximation problems, Proc. 33rd symposium on foundations of computer science (FOCS), (1992), p. 14-23 · Zbl 0977.68539 |

[6] | Bellare, M., Proof checking and approximation: towards tight results, complexity theory column, Sigact news, 27, (1996) |

[7] | Beigel, R.; Eppstein, R., 3-coloring in O(1.3446n) time: A no-MIS algorithm, Proceedings of the 36th annual IEEE symposium on foundations of computer science, (1995), p. 444-453 · Zbl 0938.68940 |

[8] | Boppana, R.; Sipser, M., The complexity of finite functions, The handbook of theoretical computer science, (1990), Elsevier Amsterdam · Zbl 0900.68268 |

[9] | Cormen, T.; Leiserson, C.; Rivest, R., Introduction to algorithms, (1990), MIT Press Cambridge |

[10] | Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S.; Szegedy, M., Approximating clique is almost NP-complete, Proc. 32nd IEEE symposium on foundations of computer science, (1991), p. 2-12 |

[11] | T. Feder, and, R. Motwani, Worst-case time bounds for coloring and satisfiability problems, manuscript, September 1998. · Zbl 1051.68076 |

[12] | Furst, M.; Saxe, J.B.; Sipser, M., Parity, circuits, and the polynomial time hierarchy, Math. systems theory, 17, 13-28, (1984) · Zbl 0534.94008 |

[13] | Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman San Francisco · Zbl 0411.68039 |

[14] | Håstad, J., Almost optimal lower bounds for small depth circuits, Proceedings of the 18th ACM symposium on theory of computing, (1986), p. 6-20 |

[15] | Håstad, J., Clique is hard to approximate within n1−ε, 37th annual symposium on foundations of computer science, (1996), p. 627-636 |

[16] | Håstad, J., Some optimal inapproxibility results, Proceedings of the twenty-ninth annual ACM symposium on theory of computing, (4-6 May 1997), p. 1-10 |

[17] | Håstad, J.; Jukna, S.; Pudlák, P., Top-down lower bounds for depth 3 circuits, Proceedings of the 34th annual IEEE symposium on foundations of computer science, (1993), p. 124-129 |

[18] | Hirsch, E.A., Two new upper bounds for SAT, ACM-SIAM symposium on discrete algorithms, (1998), p. 521-530 · Zbl 0936.68113 |

[19] | O. Kullmann, and, H. Luckhard, Deciding propositional tautologies: Algorithms and their complexity, submitted. |

[20] | Monien, B.; Speckenmeyer, E., Solving satisfiability in less than 2^n steps, Discrete appl. math., 10, 287-295, (1985) · Zbl 0603.68092 |

[21] | R. Paturi, P. Pudlák, and F. Zane, Satisfiability coding lemma, in Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, October 1997, pp. 567-574. · Zbl 0940.68049 |

[22] | R. Paturi, P. Pudlák, M. E. Saks, and F. Zane, An improved exponential-time algorithm for k-SAT, in 1998 Annual IEEE Symposium on Foundations of Computer Science, pp. 628-637. · Zbl 1297.68217 |

[23] | Paturi, R.; Saks, M.E.; Zane, F., Exponential lower bounds on depth 3 Boolean circuits, Proceedings of the 29th annual ACM symposium on theory of computing, (May 1997), p. 86-91 |

[24] | Papadimitriou, C.; Yannakakis, M., Opimization, approximation and complexity classes, J. comput. system sci., 43, 425-440, (1991) · Zbl 0765.68036 |

[25] | Razborov, A.A., Lower bounds on the size of bounded depth networks over a complete basis with logical addition, Mat. zameti, 41, 598-607, (1986) |

[26] | Sauer, N., On the density of families of sets, J. combin. theory ser. A, 13, 145-147, (1972) · Zbl 0248.05005 |

[27] | Schiermeyer, I., Solving 3-satisfiability in less than 1.579^n steps, Selected papers from CSL ’92, Lecture notes in computer science, 702, (1993), Springer-Verlag Berlin, p. 379-394 · Zbl 0788.68066 |

[28] | Schiermeyer, I., Pure literal look ahead: an O(1.497n) 3-satisfiability algorithm. workshop on the satisfiability problem, Technical report, 96-230, (April 29-May 3, 1996) |

[29] | Schöning, U., A probabilistic algorithm for k-SAT and constraint satisfaction problems, 1999 annual IEEE symposium on foundation of computer science, (1999), p. 410-414 |

[30] | Smolensky, R., Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the 19th ACM symposium on theory of computing, (1987), p. 77-82 |

[31] | Stearns, R.E.; Hunt, H.B., Power indices and easier hand problems, Math. systems theory, 23, 209-225, (1990) · Zbl 0719.68025 |

[32] | Johnson, D.S.; Szegedy, M., What are the least tractable instances of MAX clique?, ACM-SIAM symposium on discrete algorithms, (1999), p. 927-928 · Zbl 0929.68089 |

[33] | Valiant, L.G., Graph-theoretic arguments in low-level complexity, Proceedings of the 6th symposium on mathematical foundations of computer science, Lecture notes in computer science, 53, (1977), Springer-Verlag Berlin, p. 162-176 · Zbl 0384.68046 |

[34] | Van Lint, J.H., Introduction to coding theory, (1992), Springer-Verlag Berlin · Zbl 0747.94018 |

[35] | Vapnik, V.N.; Chervonenkis, A.Ya., On the uniform convergence of relative frequencies of events to their probabilities, Theory probab. appl., 16, 264-280, (1971) · Zbl 0247.60005 |

[36] | Yao, A.C-C., Separating the polynomial hierarchy by oracles, Proceedings of the 31st annual IEEE symposium on foundations of computer science, (1985), p. 1-10 |

[37] | Tarjan, R.; Trojanowski, A., Finding a maximum independent set, SIAM J. comput., 7, 537-546, (1977) · Zbl 0357.68035 |

[38] | Robson, J.M., Algorithms for maximum independent set, J. algorithms, 7, 425-440, (1986) · Zbl 0637.68080 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.