Time-space lower bounds for satisfiability
作者： Lance Fortnow , Richard Lipton , Dieter van Melkebeek , Anastasios Viglas
关键词:
摘要: We establish the first polynomial time-space lower bounds for satisfiability on general models of computation. show that any constant c less than golden ratio there exists a positive d such no deterministic random-access Turing machine can solve in time nc and space nd, where approaches 1 when does. On conondeterministic instead machines, we prove same √2.Our apply to nondeterministic linear almost all natural NP-complete problems known. In fact, they even class languages be solved n1/c.Our proofs follow paradigm indirect diagonalization. also use higher up polynomial-time hierarchy.
acm.org
unirioja.es
core.ac.uk
uchicago.edu 
sci-hub.se 参考文章(28)
Lance Fortnow, Time-Space Tradeos for Satisability Journal of Computer and System Sciences. ,(1997)
Yuri Gurevich, Saharon Shelah, Nearly linear time foundations of computer science. pp. 108- 118 ,(1989) , 10.1007/3-540-51237-3_10
Alan Woods, Bounded Arithmetic Formulas and Turing Machines of Constant Alternation Studies in logic and the foundations of mathematics. ,vol. 120, pp. 355- 377 ,(1986) , 10.1016/S0049-237X(08)70471-3
M. Ajtai, A non-linear time lower bound for Boolean branching programs foundations of computer science. pp. 60- 70 ,(1999) , 10.1109/SFFCS.1999.814578
R.J. Lipton, A. Viglas, On the complexity of SAT foundations of computer science. pp. 459- 464 ,(1999) , 10.1109/SFFCS.1999.814618
Walter L. Ruzzo, Tree-size bounded alternation Journal of Computer and System Sciences. ,vol. 21, pp. 218- 235 ,(1980) , 10.1016/0022-0000(80)90036-7
Anna R. Bruss, Albert R. Meyer, On time-space classes and their relation to the theory of real addition Theoretical Computer Science. ,vol. 11, pp. 59- 69 ,(1980) , 10.1016/0304-3975(80)90036-5
Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee, Time-space trade-off lower bounds for randomized computation of decision problems Journal of the ACM. ,vol. 50, pp. 154- 195 ,(2003) , 10.1145/636865.636867
Jose L. Balcazar, Joaquim Gabarro, Josep Diaz, Structural Complexity I ,(1988)
Joel I. Seiferas, Michael J. Fischer, Albert R. Meyer, Separating Nondeterministic Time Complexity Classes Journal of the ACM. ,vol. 25, pp. 146- 167 ,(1978) , 10.1145/322047.322061