An Improved Time-Space Lower Bound for Tautologies

Authors: S. Diehl, D. van Melkebeek, and R. Williams.
Reference: Journal of Combinatorial Optimization, 22(3): 325-338, 2011. Special issue for selected papers from the 15th International Computing and Combinatorics Conference.
Earlier version:
- S. Diehl, D. van Melkebeek, and R. Williams. An Improved Time-Space Lower Bound for Tautologies. In Proceedings of the 15th International Computing and Combinatorics Conference, pages 429-438, 2009.

Abstract

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.

dieter@cs.wisc.edu