A New TimeSpace Lower Bound for Nondeterministic Algorithms Solving Tautologies
S. Diehl, D. van Melkebeek, and R. Williams
2007
We show that for all reals c and d such that c^{2}d < 4 there exists a positive real e such that tautologies cannot be decided by both a nondeterministic algorithm that runs in time n^{c}, and a nondeterministic algorithm that runs in time n^{d} and space n^{e}. In particular, for every real d < 4^{1/3} there exists a positive real e such that tautologies cannot be decided by a nondeterministic algorithm that runs in time n^{d} and space n^{e}.
Download this report (PDF)
Return to tech report index
