文章基本信息

标题：Limits on Alternation-Trading Proofs for Time-Space Lower Bounds
本地全文：下载
作者：Sam Buss, Ryan Williams
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：This paper characterizes alternation trading based proofs that satisfiability 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 tradeoffs and lower bounds on satisfiability, we give a theoretical and computational analysis of the alternation trading proofs for 0<\epsilon<1.
关键词：alternation trading proof, lower bounds, satisfiability, time space tradeoff