On the complexity of circuit satisfiability

ABSTRACT

In this paper, we are concerned with the exponential complexity of the Circuit Satisfiability (CktSat) problem and more generally with the exponential complexity of NP-complete problems. Over the past 15 years or so, researchers have obtained a number of exponential-time algorithms with improved running times for exactly solving a variety of NP-complete problems. The improvements are typically in the form of better exponents compared to exhaustive search. Our goal is to develop techniques to prove specific lower bounds on the exponents under plausible complexity assumptions. We consider natural, though restricted, algorithmic paradigms and prove upper bounds on the success probability. Our approach has the advantage of clarifying the relative power of various algorithmic paradigms. Our main technique is a success probability amplification technique, called the Exponential Amplification Lemma, which shows that for any f(n,m)-size bounded probabilistic circuit family A that decides CktSat with success probability at least 2^{-α n} for α<1 on inputs which are circuits of size m with n variables, there is another probabilistic circuit family B that decides CktSat with size roughly f(α n, f(n,m)) and success probability about 2^{-α2 n} > 2^{-α n}.

In contrast, the standard method for boosting success probability by repeated trials will improve it to (1-(1-2^{-α n})^t) (approx t2^{-α n} for t=O(2^{α n})) using circuits of size about tf(n,m).

Using this lemma, we derive tight bounds on the exponent of the success probability for deciding the CktSat problem in a variety of probabilistic computational models under complexity assumptions. For example, we show that the success probability cannot be better than 2^-n+o(n) for deciding CktSat by probabilistic polynomial size circuits unless CktSat (thereby all of NP) for polynomial size instances can be decided by 2^nμ size deterministic circuits for some μ <1, which is considered an unlikely event. As another example, we show that probabilistic quasilinear size circuits cannot achieve success probability better than 2^-n+o(n) unless CktSat (as well as NP) has O(m^{O(lg lg m)}) size deterministic circuits, which is very close to the statement NP ⊆ P/poly, an unlikely scenario.

References

1. Karl R. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-parameter tractability and completeness iv: On completeness for w{p} and pspace analogues. Ann. Pure Appl. Logic, 73(3):235--276, 1995.
2. Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In STOC '01, 601--610, 2001.
3. Richard Beigel. Finding maximum independent sets in sparse and general graphs. In SODA '99, 856--857, 1999.
4. Richard Beigel and David Eppstein. 3-coloring in time o(1.3446ⁿ): A no-mis algorithm. In FOCS '95,444--452, 1995.
5. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM, 9(1):61--63, 1962.
6. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets möbius: Fast subset convolution. In STOC '07, 67--74, 2007.
7. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Computing the tutte polynomial in vertex-exponential time. In FOCS '08,677--686, 2008.
8. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM Journal of Computing, 39(2):546--563, 2009.
9. Hans Bodlaender and Dieter Kratsch. An exact algorithm for graph coloring with polynomial memory. Technical Report UU-CS-2006-015, Utrecht University, 2006.
10. Richard P. Brent, Fred G. Gustavson, and David Y. Y. Yun. Fast solution of toeplitz systems of equations and computation of padé approximants. J. Algorithms, 1(3):259--295, 1980.
11. J. M. Byskov. Exact Algorithms for Graph Colouring and Exact Satisfiability. PhD thesis, Aarhus University, August 2005.
12. Jesper Makholm Byskov. Algorithms for k-colouring and finding maximal independent sets. In SODA '03, 456--457, 2003.
13. Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci., 72(8):1346--1367, 2006.
14. Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan, and Uwe Schöning. A deterministic (2 -- 2/(k 1))ⁿ algorithm for k-sat based on local search. Theoretical Computer Science, 289(1):69--83, 2002.
15. David Eppstein. Improved algorithms for 3--coloring, 3-edge-coloring, and constraint satisfaction. In SODA '01, 329--337, 2001.
16. David Eppstein. Small maximal independent sets and faster exact graph coloring. Journal of Graph Algorithms and Applications, 7:131--140, 2003.
17. David Eppstein. Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. ACM Trans. Algorithms, 2(4):492--509, 2006.
18. F. Fomin, F. Grandoni, and D. Kratsch. Measure and conquer : a simple o(2^0.288n) independent set algorithm. In SODA '06, 18--25, 2006.
19. Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, and Peter Rossmanith. Worst-case upper bounds for max-2-sat with an application to max-cut. Discrete Applied Mathematics, 130(2):139--155, 2003.
20. Michael Held and Richard M. Karp. A dynamic programming approach to sequencing problems. In Proceedings of the 1961 16th ACM national meeting, 71.201--71.204, 1961.
21. R. Impagliazzo and R. Paturi. The complexity of k-sat. Journal of Computer and Systems Sciences, 62(2):367--375, March 2001.
22. R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63:512--530, 1998.
23. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography with constant computational overhead. In STOC '08, 433--442, 2008.
24. E. Kaltofen and A. Lobo. On rank properties of toeplitz matrices over finite fields. In ISSAC '96, 241--249, 1996.
25. Richard M. Karp. Dynamic programming meets the principle of inclusion and exclusion. Operations Research Letters, 1:49--51, April 1982.
26. Ioannis Koutis. Faster algebraic algorithms for path and packing problems. In ICALP '08, 575--586, 2008.
27. E. Lawler. A note on the complexity of the chromatic number problem. Information Processing Letters, 5(3):66--67, 1976.
28. Dániel Marx. Can you beat treewidth? In FOCS '07, 169--179, 2007.
29. Dániel Marx. On the optimality of planar and geometric approximation schemes. In FOCS '07, 338--348, 2007.
30. Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In STOC '10, 2010. To appear.
31. Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the shortest vector problem. In SODA '10, 1468--1480, 2010.
32. Victor Pan. Structured Matrices and Polynomials: Unified Superfast Algorithms. Birkhauser, 2001.
33. R. Paturi, P. Pudlák, and F. Zane. Satisfiability coding lemma. Chicago Journal of Theoretical Computer Science, December 1999.
34. Nicholas Pippenger. Fast simulation of combinational logic circuits without random-access storage. In Fifteenth Allerton Conference, 25--33, 1977.
35. Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. ACM, 26(2):361--381, 1979.
36. J. M. Robson. Algorithms for maximum independent sets. Journal of Algorithms, 7:425--440, September 1986.
37. Michael E. Saks. Space efficient algorithms for np-hard sequencing and partition problems. manuscript, November 1998.
38. Claus-Peter Schnorr. Satisfiability is quasilinear complete in nql. J. ACM, 25(1):136--145, 1978.
39. U. Schöning. A probabilistic algorithm for k-sat and constraint satisfaction problems. In FOCS '99, 410--414, 1999.
40. Richard Edwin Stearns and Harry B. Hunt. Power indices and easier hard problems. Mathematical Systems Theory, 23(4):209--225, 1990.
41. Patrick Traxler. The time complexity of constraint satisfaction. In 2008 Dagstuhl Workshop on Moderately Exponential-time Algorithms, 2008.
42. L. Valiant and V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85--93, 1986.
43. Dieter van Melkebeek. A survey of lower bounds for satisfiability and related problems. Electronic Colloquium on Computational Complexity (ECCC), 14(099), 2007.
44. Ryan Williams. Finding paths of length k in O*(2^k) time. Information Processing Letters, 109(6):315--318, 2009.

Index Terms

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes