## DIMACS TR: 2000-06

## Time-Space Tradeoffs for Nondeterministic Computation

### Authors: Lance Fortnow and Dieter van Melkebeek

**
ABSTRACT
**

We show new lower bounds for satisfiability and nondeterministic
linear time. Satisfiability cannot be solved on general purpose
random-access Turing machines in time *n*^{1.618}
and space *n*^{o(1)}. This improves recent results of
Fortnow and of Lipton and Viglas.

In general, for any constant *a* less than the golden ratio, we
prove that satisfiability cannot be solved in time
*n*^{a} and space *n*^{b} for some positive
constant *b*. Our techniques allow us to establish this result
for *b* < *((a+2)/a*^{2}-a)/2. We can do better for
*a* close to the golden ratio, for example, satisfiability cannot
be solved by a random-access Turing machine using
*n*^{1.46} time and *n*^{.11} space.
We also show the first nontrivial lower bounds on machines using
sublinear space. For example, there exists a language computable in
nondeterministic linear time and *n*^{.619} space that
cannot be computed in deterministic *n*^{1.618} time and
*n*^{o(1)} space.

Higher up the polynomial-time hierarchy we can get better bounds. We
show that linear-time alternating computations with a most *k*
alternations require essentially *n*^{k} time if we only allow
*n*^{o(1)} space. We also show new lower bounds on
conondeterministic versus nondeterministic computation.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-06.ps.gz

DIMACS Home Page