21 - Cosmology and complexity

Summary

Puzzle from last chapter: What can you compute with “narrow” CTCs that only send one bit back in time?

Solution: let x be a chronology-respecting bit, and let y be a CTC bit. Then, set x := x ⊕ y and y := x. Suppose that Pr[x = 1] = p and Pr[y = 1] = q. Then, causal consistency implies p = q. Hence, Pr[x ⊕ y = 1] = p(1 - q) + q(1 - p) = 2p(1 - p).

So we can start with p exponentially small, and then repeatedly amplify it. We can thereby solve NP-complete problems in polynomial time (and indeed PP ones also, provided we have a quantum computer).

I’ll start with the “New York Times model” of cosmology – that is, the thing that you read about in popular articles until fairly recently – which says that everything depends on the density of matter in the universe. There’s this parameter Ω which represents the mass density of the universe, and if it’s greater than unity, the universe is closed. That is, the matter density of the universe is high enough that, after the Big Bang, there has to be a Big Crunch. Furthermore, if Ω > 1, spacetime has a spherical geometry (positive curvature). If Ω = 1, the geometry of spacetime is flat and there’s no Big Crunch. If Ω < 1, then the universe is open, and has a hyperbolic geometry. The view was that these are the three cases.