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

Start Free Trial

No credit card required