A New Time-Space Lower Bound for Nondeterministic Algorithms Solving Tautologies

We show that for all reals c and d such that c²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