13
$\begingroup$

Following the discussion on lower bounds for 3SAT [1], 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] by Ryan Williams.)

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).

$\endgroup$
5
  • 1
    $\begingroup$ hmm. another example of not needing the CW tag. $\endgroup$ Sep 1, 2010 at 16:39
  • $\begingroup$ What do you mean? $\endgroup$ Sep 1, 2010 at 17:05
  • 1
    $\begingroup$ 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"? $\endgroup$ Sep 1, 2010 at 21:06
  • $\begingroup$ 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. $\endgroup$ Sep 1, 2010 at 23:12
  • 2
    $\begingroup$ 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 $\endgroup$ Sep 2, 2010 at 2:25

1 Answer 1

12
$\begingroup$

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

Duris and Galil (1984) 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) showed that the same lower bound holds for the element distinctness problem.

Babai, Nisan, and Szegedy (1989) 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) 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) proves time-space tradeoffs for randomized computations.

Santhanam (2001) showed that $TS \geq \Omega(n^2)$ holds for multitape Turing machines solving SAT, building on Cobham's analogous lower bound for PALINDROMES.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.