Time-space lower bounds for satisfiability

ABSTRACT

We establish the first polynomial time-space lower bounds for satisfiability on general models of computation. We show that for any constant c less than the golden ratio there exists a positive constant d such that no deterministic random-access Turing machine can solve satisfiability in time n^c and space n^d, where d approaches 1 when c does. On conondeterministic instead of deterministic machines, we prove the same for any constant c less than &2radic;.Our lower bounds apply to nondeterministic linear time and almost all natural NP-complete problems known. In fact, they even apply to the class of languages that can be solved on a nondeterministic machine in linear time and space n^1/c.Our proofs follow the paradigm of indirect diagonalization. We also use that paradigm to prove time-space lower bounds for languages higher up in the polynomial-time hierarchy.

REFERENCES

• 1: Miklos Ajtai, A Non-Linear Time Lower Bound for Boolean Branching Programs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.60, October 17-18, 1999
• 2: Eric Allender , Michal Koucký , Detlef Ronneburger , Sambudda Roy , V. Vinay, Time-Space Tradeoffs in the Counting Hierarchy, Proceedings of the 16th Annual Conference on Computational Complexity, p.295, June 18-21, 2001
• 3: Balcázar, J., Díaz, J., and Gabarró, J. 1995. Structural Complexity I. EATCS Monographs on Theoretical Computer Science, vol. 11. Springer-Verlag; New York.
• 4: Paul Beame , Michael Saks , Xiaodong Sun , Erik Vee, Time-space trade-off lower bounds for randomized computation of decision problems, Journal of the ACM (JACM), v.50 n.2, p.154-195, March 2003 [doi>10.1145/636865.636867]
• 5: Bruss, A., and Meyer, A. 1980. On time-space classes and their relation to the theory of real addition. Theoret. Comput. Sci. 11, 59--69.
• 6: Stephen A. Cook, Short propositional formulas represent nondeterministic computations, Information Processing Letters, v.26 n.5, p.269-270, Jan. 11, 1988 [doi>10.1016/0020-0190(88)90152-4 ]
• 7: Fortnow, L. 2000a. Diagonalization. Bull. Europ. Assoc. Theoret. Comput. Sci. 71, 102--112.
• 8: Lance Fortnow, Time—space tradeoffs for satisfiability, Journal of Computer and System Sciences, v.60 n.2, p.337-353, April 2000 [doi>10.1006/jcss.1999.1671 ]
• 9: Lance Fortnow , Carsten Lund, Interactive proof systems and alternating time-space complexity, Theoretical Computer Science, v.113 n.1, p.55-73, May 24, 1993
• 10: Lance Fortnow , Dieter Van Melkebeek, Time-Space Tradeoffs for Nondeterministic Computation, Proceedings of the 15th Annual IEEE Conference on Computational Complexity, p.2, July 04-07, 2000
• 11: Y. Gurevich , S. Shelah, Nearly linear time, Logic at Botik'89 Symposium on logical foundations of computer science, Springer-Verlag New York, Inc., New York, NY, 1989
• 12: F. C. Hennie , R. E. Stearns, Two-Tape Simulation of Multitape Turing Machines, Journal of the ACM (JACM), v.13 n.4, p.533-546, Oct. 1966 [doi>10.1145/321356.321362]
• 13: Kannan, R. 1984. Towards separating nondeterminism from determinism. Math. Syst. Theory 17, 29--45.
• 14: Richard J. Lipton , Anastasios Viglas, On the Complexity of SAT, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.459, October 17-18, 1999
• 15: Papadimitriou, C. 1994. Computational Complexity. Addison-Wesley, Reading, MA.
• 16: Paul, W., Pippenger, N., Szemeridi, E., and Trotter, W. 1983. On determinism versus non-determinism and related problems. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 429--438.
• 17: Paul, W., Prauß, E., and Reischuk, R. 1980. On alternation. Acta Inf. 14, 243--255.
• 18: Nicholas Pippenger , Michael J. Fischer, Relations Among Complexity Measures, Journal of the ACM (JACM), v.26 n.2, p.361-381, April 1979 [doi>10.1145/322123.322138]
• 19: C. P. Schnorr, Satisfiability Is Quasilinear Complete in NQL, Journal of the ACM (JACM), v.25 n.1, p.136-145, Jan. 1978 [doi>10.1145/322047.322060]
• 20: Joel I. Seiferas , Michael J. Fischer , Albert R. Meyer, Separating Nondeterministic Time Complexity Classes, Journal of the ACM (JACM), v.25 n.1, p.146-167, Jan. 1978 [doi>10.1145/322047.322061]
• 21: Tourlakis, I. 2001. Time-space lower bounds for SAT on nonuniform machines. J. Comput. Syst. Sci. 63, 2, 268--287.
• 22: van Melkebeek, D. 2004. Time-space lower bounds for NP-complete problems. In Current Trends in Theoretical Computer Science, G. Paun, G. Rozenberg, and A. Salomaa, Eds. World Scientific, 265--291.
• 23: van Melkebeek, D., and Raz, R. 2004. A time lower bound for satisfiability. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming. Springer-Verlag, New York, 971--982.
• 24: Žàk, S. 1983. A Turing machine time hierarchy. Theoret. Comput. Sci. 26, 327--333.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
      F.2.3 Tradeoffs among Complexity Measures

General Terms:
Theory

Keywords:
Complexity of satisfiability, time-space lower bounds