LIMITS ON ALTERNATION TRADING PROOFS FOR TIME-SPACE LOWER BOUNDS

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(is an element of)), for various values c < 2 and is an element of < 1. We characterize exactly what can be proved in the is an element of = 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 < is an element of < 1.