- 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 *n*^{c} and space *n*^{d}, 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 *n*^{1/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.