- Authors: L. Fortnow, R. Lipton, D. van Melkebeek, and A. Viglas.
- Reference: Journal of the ACM, 52: 835-865, 2005.
- Earlier version:
- L. Fortnow and D. van Melkebeek.
Time-Space Tradeoffs for
Nondeterministic Computation. In
Proceedings of the 15th IEEE Conference on Computational
Complexity, pages 2-13, 2000. Invited to the special issue of
the Journal of Computer and System Sciences for selected
papers from the conference.
Abstract
We establish the first polynomial time-space lower bounds for satisfiability
on general models of computation. We show that for any constant c
less than the golden ratio there exists a positive constant d such
that no deterministic random-access Turing machine can solve satisfiability
in time nc and space nd, where d
approaches 1 when c does. On conondeterministic instead of
deterministic machines, we prove the same for any constant c less
than √ 2.
Our lower bounds apply to nondeterministic linear time and almost all natural
NP-complete problems known. In fact, they even apply to the class of
languages that can be solved on a nondeterministic machine in linear time
and space n1/c.
Our proofs follow the paradigm of indirect diagonalization. We also use that
paradigm to prove time-space lower bounds for languages higher up in the
polynomial-time hierarchy.
