<p>Here are a few additional references. More can be found by looking at the papers that cite these.</p>

<p><a href="http://www.ams.org/mathscinet-getitem?mr=0738748">Duris and Galil (1984)</a> give a language in $P$ which requires $T^2 S \geq \Omega(n^3)$ on one-tape Turing machines with any constant number of read-write heads. <a href="http://linkinghub.elsevier.com/retrieve/pii/0304397586901507">Karchmer (1986)</a> showed that the same lower bound holds for the <em>element distinctness</em> problem. </p>

<p><a href="http://portal.acm.org/citation.cfm?id=73007.73008">Babai, Nisan, and Szegedy (1989)</a> give a very natural language (generalized inner product) that is solvable in $O(n)$ time and $O(1)$ space on a $k+1$-head one-tape Turing machine, that requires $T S \geq \Omega(n^2)$ on any $k$-head one-tape Turing machine.</p>

<p><a href="http://portal.acm.org/citation.cfm?id=301424">Ajtai (1999)</a> shows time-space tradeoffs for deterministic random access machines computing element distinctness. In particular if $S \leq o(n)$, then $T \geq \omega(n)$. Subsequent work by <a href="http://www.cs.washington.edu/homes/beame/papers/randomts.ps">Beame, Saks, Sun, and Vee (2000)</a> proves time-space tradeoffs for randomized computations.</p>

<p><a href="http://dx.doi.org/10.1016/S0020-0190%2800%2900227-1">Santhanam (2001)</a> showed that $TS \geq \Omega(n^2)$ holds for multitape Turing machines solving SAT, building on Cobham's analogous lower bound for PALINDROMES. </p>

CC BY-SA 2.5
2010-09-02T00:42:22.343Z
2010-09-02T00:42:22.343Z
Ryan Williams
<p>Following the discussion on lower bounds for 3SAT [<a href="https://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat">1</a>], I'm wondering what are the main lower bound results formulated as space-time tradeoffs.  I'm excluding results such as, say, Savitch's theorem; a good entry would focus on a single problem and its bounds.  An example would be :</p>
<p>&quot;Let T and S be the running time and space bound of any SAT algorithm. Then we must have T⋅S≥n2cos(π/7)−o(1) infinitely often.&quot; (Given in [<a href="https://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat">1</a>] by Ryan Williams.)</p>
<p>or</p>
<p>&quot;SAT cannot be solved simultaneously in n<sup>1+0(1)</sup> time and
n<sup>1-ε</sup> space for any ε&gt;0 on general
random-access nondeterministic Turing machines.&quot; (Lance Fortnow in 10.1109/CCC.1997.612300)</p>
<p>Further, I'm including <em>definitions</em> of natural space-time tradeoff complexity classes (excluding circuit classes).</p>

CC BY-SA 2.5
2010-09-01T16:39:37.723Z
hmm. another example of not needing the CW tag.
Suresh Venkat
CC BY-SA 2.5
2010-09-01T17:05:58.793Z
What do you mean?
Michaël Cadilhac
CC BY-SA 2.5
2010-09-01T21:06:06.310Z
Suresh is saying that you don't have to put "community wiki" on this question, if you rephrase the question to be something other than a big list, and were more specific about what you're looking for. Also, is it really a "soft question"?
Ryan Williams
CC BY-SA 2.5
2010-09-01T23:12:24.397Z
Well, I do want a big list, and the question not being specific is, I think, a good way to get one.  Is this kind of list prohibited?  (I can pretty much deduce that I did something wrong, as no answer has been given, but don't know what.)
Also, this is a soft question as it doesn't require any intellectual work.
Michaël Cadilhac
CC BY-SA 2.5
2010-09-02T02:25:30.273Z
We hope to clarify this eventually in the FAQ. I'd say that this is not a soft question because it's technical. A soft question is more about topics around research - where to go to grad school, how to read papers, etc
Suresh Venkat
<cc.complexity-theory><ds.algorithms><big-list><space-time-tradeoff>
Space-time tradeoff lower bounds
Michaël Cadilhac
# Space-time tradeoff lower bounds

(Asked by: username_0 on 2010-09-01)

Following the discussion on lower bounds for 3SAT [[1](https://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat)], I'm wondering what are the main lower bound results formulated as space-time tradeoffs. I'm excluding results such as, say, Savitch's theorem; a good entry would focus on a single problem and its bounds. An example would be :

"Let T and S be the running time and space bound of any SAT algorithm. Then we must have T⋅S≥n2cos(π/7)−o(1) infinitely often." (Given in [[1](https://cstheory.stackexchange.com/questions/93/what-are-the-best-current-lower-bounds-on-3sat)] by username_2.)

or

"SAT cannot be solved simultaneously in n1+0(1) time and
n1-ε space for any ε>0 on general
random-access nondeterministic Turing machines." (Lance Fortnow in 10.1109/CCC.1997.612300)

Further, I'm including *definitions* of natural space-time tradeoff complexity classes (excluding circuit classes).

**Tags:** cc.complexity-theory, ds.algorithms, big-list, space-time-tradeoff

> **Comments:**
> **username_1**: hmm. another example of not needing the CW tag.  
> **username_0**: What do you mean?  
> **username_2**: Suresh is saying that you don't have to put "community wiki" on this question, if you rephrase the question to be something other than a big list, and were more specific about what you're looking for. Also, is it really a "soft question"?  
> **username_0**: Well, I do want a big list, and the question not being specific is, I think, a good way to get one.  Is this kind of list prohibited?  (I can pretty much deduce that I did something wrong, as no answer has been given, but don't know what.) Also, this is a soft question as it doesn't require any intellectual work.  
> **username_1**: We hope to clarify this eventually in the FAQ. I'd say that this is not a soft question because it's technical. A soft question is more about topics around research - where to go to grad school, how to read papers, etc  

---

## 1 answers

### Answer by username_2 on 2010-09-02. Score: 12 | Accepted answer

Here are a few additional references. More can be found by looking at the papers that cite these.

[Duris and Galil (1984)](http://www.ams.org/mathscinet-getitem?mr=0738748) give a language in $P$ which requires $T^2 S \geq \Omega(n^3)$ on one-tape Turing machines with any constant number of read-write heads. [Karchmer (1986)](http://linkinghub.elsevier.com/retrieve/pii/0304397586901507) showed that the same lower bound holds for the *element distinctness* problem.

[Babai, Nisan, and Szegedy (1989)](http://portal.acm.org/citation.cfm?id=73007.73008) give a very natural language (generalized inner product) that is solvable in $O(n)$ time and $O(1)$ space on a $k+1$-head one-tape Turing machine, that requires $T S \geq \Omega(n^2)$ on any $k$-head one-tape Turing machine.

[Ajtai (1999)](http://portal.acm.org/citation.cfm?id=301424) shows time-space tradeoffs for deterministic random access machines computing element distinctness. In particular if $S \leq o(n)$, then $T \geq \omega(n)$. Subsequent work by [Beame, Saks, Sun, and Vee (2000)](http://www.cs.washington.edu/homes/beame/papers/randomts.ps) proves time-space tradeoffs for randomized computations.

[Santhanam (2001)](http://dx.doi.org/10.1016/S0020-0190%2800%2900227-1) showed that $TS \geq \Omega(n^2)$ holds for multitape Turing machines solving SAT, building on Cobham's analogous lower bound for PALINDROMES.


---

