Skip to main content
1 of 3
Post Made Community Wiki
Ryan Williams
  • 4.7k
  • 27
  • 38

I think Lance's choices from the past are pretty comprehensive, although I might add a couple more from the lower bounds department which for some reason are not well-known:

John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant: On Time Versus Space. J. ACM 24(2): 332-337 (1977)

Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter: On Determinism versus Non-Determinism and Related Problems (Preliminary Version) FOCS 1983: 429-438

The first paper shows that $TIME[t] \subseteq SPACE[t/\log t]$ (so, $SPACE[t]$ is not contained in $TIME[o(t \log t)]$). This result has since been generalized (from Turing machines) to all the "modern" models of computation. (For references, look at citations on Google scholar.)

The second paper shows that for multitape Turing machines, $NTIME[n] \neq TIME[n]$. This is really the only generic separation of nondeterministic and deterministic time that we know. It is not known whether this result extends to more modern models of computation. Perhaps one reason why these results are not better known is that many seem to believe that their approaches are a dead end, more or less. (There's some mathematical evidence for that: the techniques do break down if you try to push them any further, but it's always possible these techniques could be combined with something new.)

As for the last 6 years, I'll have to think about my choices for the "best 6 papers" since then. Expect an update to this answer later.

Ryan Williams
  • 4.7k
  • 27
  • 38