Computational complexity and time travel

I’ve already put this Scott Aaronson paper in Assorted Links, but here are two passages I liked in particular:

…finding a fixed point might require Nature to solve an astronomically-hard computational problem! To illustrate, consider a science-fiction scenario wherein you go back in time and dictate Shakespeare’s plays to him. Shakespeare thanks you for saving him the effort, publishes verbatim the plays that you dictated, and centuries later the plays come down to you, whereupon you go back in time and dictate them to Shakespeare, etc. Notice that, in contrast to the grandfather paradox, here there is no logical contradiction: the story as we told it is entirely consistent. But most people find the story “paradoxical” anyway. After all, somehow Hamlet gets written, without anyone ever doing the work of writing it! As Deutsch perceptively observed, if there is a “paradox” here, then it is not one of logic but of computational complexity…

And:

Now, some people have asked how such a claim could possibly be consistent with modern physics. For didn’t Einstein teach us that space and time are merely two aspects of the same structure? One immediate answer is that, even within relativity theory, space and time are not interchangeable: space has a positive signature whereas time has a negative signature. In complexity theory, the difference between space and time manifests itself in the straightforward fact that you can reuse the same memory cells over and over, but you can’t reuse the same moments of time.

Yet, as trivial as that observation sounds, it leads to an interesting thought. Suppose that the laws of physics let us travel backwards in time. In such a case, it’s natural to imagine that time would become a “reusable resource” just like space is—and that, as a result, arbitrary PSPACE computations would fall within our grasp. But is that just an idle speculation, or can we rigorously justify it?

It is in general quite an interesting paper.