Limits on Alternation Trading Proofs for Time–Space Lower Bounds

详细信息    查看全文

• 作者：Samuel R. Buss ; Ryan Williams
• 关键词：Satisfiability ; alternation trading proofs ; time–space trade ; offs ; lower bounds ; 68Q15 ; 68Q17
• 刊名：Computational Complexity
• 出版年：2015
• 出版时间：September 2015
• 年：2015
• 卷：24
• 期：3
• 页码：533-600
• 全文大小：717 KB
• 参考文献：Scott Aaronson & Avi Wigderson (2009). Algebrization: A New Barrier in Complexity Theory. ACM Transactions on Computation Theory 1(1).
  Theodore Baker, John Gill & Robert Solovay (1975). Relativizations of the P=?NP Question. SIAM Journal on Computing 4, 431-42.
  James Bennett (1962). On Spectra. Ph.D. thesis, Princeton University.
  Scott Diehl & Dieter van Melkebeek (2006). Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines. SIAM Journal on Computing 36, 563-94.
  Lance Fortnow (1997). Nondeterministic Polynomial Time Versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability. In Proc. IEEE Conference on Computational Complexity (CCC), 52-0.
  Lance Fortnow, Richard Lipton, Dieter van Melkebeek & Anastasios Viglas (2005). Time-Space Lower Bounds for Satisfiability. Journal of the ACM 52(6), 835-65.
  Lance Fortnow & Dieter van Melkebeek (2000). Time-Space Tradeoffs for Nondeterministic Computation. In Proc. IEEE Conference on Computational Complexity (CCC), 2-3.
  Kannan Ravi: Towards Separating Nondeterminism from Determinism. Mathematical Systems Theory 17, 29-5 (1984)MATH MathSciNet View Article
  Richard Lipton & Anastasios Viglas (1999). On the Complexity of SAT. In Proc. 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 459-64.
  Dieter van Melkebeek (2004). Time-Space Lower Bounds for NPComplete Problems. In Current Trends in Theoretical Computer Science, 265-91. World Scientific.
  Dieter van Melkebeek (2007). A Survey of Lower Bounds for Satisfiability and Related Problems. Foundations and Trends in Theoretical Computer Science 2(3), 197-03.
  Dieter van Melkebeek & Ran Raz (2005). A Time Lower Bound for Satisfiability. Theoretical Computer Science 348, 311-20.
  V. A. Nepomnja??i? (1970). Rudimentary Predicates and Turing Computations. Dokl. Akad. Nauk SSSR 195, 282-84. English translation in Soviet Math. Dokl. 11 (1970) 1462-465.
  Alexander A. Razborov & Steven Rudich (1997). Natural Proofs. Journal of Computer and System Sciences 55(1), 24-5.
  Iannis Tourlakis: Time-Space Tradeoffs for SAT and Related Problems. Journal of Computer and System Sciences 63(2), 268-87 (2001)MATH MathSciNet View Article
  Ryan Williams: Inductive Time-Space Lower Bounds for SAT and Related Problems. Computational Complexity 15(4), 433-70 (2006)MATH MathSciNet View Article
  Ryan Williams: Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. Computational Complexity 17(2), 179-19 (2008)MATH MathSciNet View Article
  Ryan Williams (2010). Alternation-Trading Proofs, Linear Programming, and Lower Bounds. In Proc. 27th Intl. Symp. on Theory of Computings (STACS 2010), 669-80.
  Ryan Williams (2013). Alternation-Trading Proofs, Linear Programming, and Lower Bounds. ACM Transactions of Computation Theory 5(2), article 6.
  
• 作者单位：Samuel R. Buss (1)
  Ryan Williams (2)
  
  1. Department of Mathematics, University of California, San Diego La Jolla, CA, 92093-0112, USA
  2. Computer Science Department, Stanford University, Stanford, CA, 94305, USA
  
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Computational Mathematics and Numerical Analysis
  
• 出版者：Birkh盲user Basel
• ISSN：1420-8954

文摘

This paper characterizes alternation trading-based proofs that the Boolean satisfiability problem is not in the time- and space-bounded class DTISP\({(n^c,n^\epsilon)}\), for various values c <?2 and \({\epsilon < 1}\). We characterize exactly what can be proved in the \({\epsilon = 0}\) case with currently known methods and prove the conjecture of Williams that \({c=2\cos(\pi/7)}\) is optimal for this. For time–space trade-offs and lower bounds on satisfiability, we give a theoretical and computational analysis of the alternation trading proofs for \({0 < \epsilon < 1}\).