- Authors: D. van Melkebeek and R. Raz.
- Reference: Theoretical Computer Science, 348: 311-320, 2005.
Special issue dedicated to papers selected from the
31st International Colloquium on Automata, Languages and
Programming.
- Earlier version:
Abstract
We show that a deterministic Turing machine with one d-dimensional
work tape and random access to the input cannot solve satisfiability
in time na for
a < ((d+2)/(d+1))1/2.
For conondeterministic machines, we obtain a similar lower bound for any
a such that
a3 < 1 + a/(d+1).
The same bounds apply to almost all natural NP-complete problems known.
