Limits on Alternation-Trading Proofs for Time-Space Lower Bounds
Samuel R. Buss, Ryan Williams · 2012
This paper characterizes alternation trading based proofs that the satisfiability problem is not in the time and space bounded class DTISP(nc, nϵ), for various values c <; 2 and ϵ <; 1. We characterize exactly what can be proved for ϵ ∈ o(1) with currently known methods, and prove the conjecture of Williams that the best known lower bound exponent c = 2 cos(π/7) is optimal for alternation trading proofs. For general time-space tradeoff lower bounds on satisfiability, we give a theoretical and computational analysis of the alternation trading proofs for 0 <; ϵ <; 1, again proving time lower bounds for various values of ϵ which are optimal for the alternation trading proof paradigm.