Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ALTERNATION TRADING PROOF:
Reports tagged with alternation trading proof:
TR11-031 | 8th March 2011
Sam Buss, Ryan Williams

Limits on Alternation-Trading Proofs for Time-Space Lower Bounds

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 ... more >>>




ISSN 1433-8092 | Imprint