13

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

Community
  • 1
Michaël Cadilhac
  • 3,946
  • 22
  • 39
  • 1
    hmm. another example of not needing the CW tag. – Suresh Venkat Sep 01 '10 at 16:39
  • What do you mean? – Michaël Cadilhac Sep 01 '10 at 17:05
  • 1
    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 Sep 01 '10 at 21:06
  • 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 Sep 01 '10 at 23:12
  • 2
    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 Sep 02 '10 at 02:25

1 Answers1

12

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.

Ryan Williams
  • 27,465
  • 7
  • 115
  • 164