Google Analytics

Saturday, June 10, 2006

Time-Travel Circuits

From Computing Like Gods by Jörn Grote
Time travel circuits had been in the first stages of development, but even then it was clear that we had cracked NP complexity. Before TTCs, solving computational problems from the NP-class in polynomial time was like finding the holy grail. And then we got TTCs. They utilized extremely small wormholes, were one opening had been accelerated near the speed of light.

Computers with time travel circuits could easily solve NP-complex problems in polynomial time, but the limit was actually PSPACE. Time travel was characterized by the computational complexity class of PSPACE, a class of problems that was either bigger or at least as big as the NP class.

When the news were out that they had TTCs, most people had no idea what it meant. I can still remember the headlines TIME TRAVEL IS REAL, WE CAN GO BACK, KILL YOUR GRANDFATHER. Naturally all these articles omitted the fact what we really could do with TTCs. It was cheap and easy to create the extremely small wormholes, but bigger ones grew unstable with rising size. The crater where once had been Calcutta tells you that they had found the limit and surpassed it.

22 comments:

  1. I'm impressed: Grote gets it exactly right, and the reason he's right is not entirely trivial. Indeed, if quantum computers are allowed in the closed timelike curve, then the reason PSPACE is the limit involves Taylor expansions and Csanky's algorithm for the determinant.

    (Reference: A. and Watrous, in preparation...)

    ReplyDelete
  2. If we could solve NP-hard problems in linear time we could resolve the P vs. NP issue. Or, for that matter, resolve any mathematical problem that might have a proof at a set limit of 200 or so pages.

    Because proofs are polynomial-time verifiable, having such a machine effectively allows you to generate proofs. Part of the story seems to imply the author was aware of this.

    ReplyDelete
  3. Er, I meant polynomial, not linear time.

    ReplyDelete
  4. Should we be impressed? Is there any science fiction where the writing is even halfway decent?

    ReplyDelete
  5. Should we be impressed? Is there any science fiction where the writing is even halfway decent?

    Nicholson Baker. Kurt Vonnegut. Philip K. Dick. Orson Scott Card.

    I rest my case.

    ReplyDelete
  6. Macneil,

    How did you learn so much about this math?

    ReplyDelete
  7. Is there any science fiction where the writing is even halfway decent?

    Counterquestion: Is there any non-SF worth reading?

    In regard to the story, I got the idea from Scott Aaronson's NP-complete Problems and Physical Reality, which I think I found here last year. The title of the story is a pointer to Aaronson's words near the end of the paper "So if we could solve the general case - if knowing something was tantamount to knowing the shortest
    efficient description of it - then we would be almost like gods.
    "

    In reagard to PSPACE, the paper said it only charaterized classical computational complexity of time travel, quantum computational complexity was charaterized by another class, I think BQP_CTC, which contained PSPACE, but indicated that the reverse might not be true. So, I left that stuff out of the story and assumed they had only classical computers and wormholes.

    ReplyDelete
  8. Counterquestion: Is there any non-SF worth reading?

    Uhh... yes. I'll start with not reading the kind that uses "were" incorrectly twice in three paragraphs. The first occurrence should be "where" and the second should be "was."

    ReplyDelete
  9. Charles Stross uses time-travel circuits as a prop in his novel _Singularity Sky_. Unfortunately, the complexity issues are not considered in any depth. One could attempt to explain this by the fact that the novel features an angry future intelligence that looks askance at attempts by humanity to use TTCs.

    Stross treats P vs NP more explicitly in _The Atrocity Archives_, but regrettably the discussion is a tiny bit off...not that it matters much for the rest of the story.

    ReplyDelete
  10. In Stross's story "Antibodies" a proof for P=PN is discovered and triggers the emergence of AI among other things.

    ReplyDelete
  11. Crater.

    Calcutta.

    (thinks for a while)

    never mind!

    ReplyDelete
  12. Isn't time travel (to the future and back) implies that any recursive function can be computed in constant time? :)

    ReplyDelete
  13. I'll start with not reading the kind that uses "were" incorrectly twice in three paragraphs. The first occurrence should be "where" and the second should be "was."

    Not to mention the one in the following paragraph. Thank god we can travel back in time and correct it!

    -ff

    ReplyDelete
  14. Regarding misuse of "were" -- you're forgetting to account for language drift between current day and the time in which the protagonist exists. The Great Tense Shift of the late 21st century explains the replace of "was" with "were" (optionally, not required). The dropping of the "h" from "where" is simply a regionalism.

    "In the 23rd century, we don't need editors!"

    ReplyDelete
  15. More subtly, but perhaps more disturbring to read, are the awkward shifts into and out of the pluperfect.

    ReplyDelete
  16. Isn't time travel (to the future and back) implies that any recursive function can be computed in constant time? :)

    No. You still have a space limitation (namely, how many bits you can send through the closed timelike curve).

    ReplyDelete

  17. No. You still have a space limitation (namely, how many bits you can send through the closed timelike curve).


    But isn't sending back to the past only one bit suffices?

    ReplyDelete
  18. But isn't sending back to the past only one bit suffices?

    Yes, if you don't count all the computation you will do in the future as part of the resource bound! But I don't think that's fair. It's like maxing out your credit card and not counting the bill.

    If you can only do a polynomial amount of computation before going back in time, then the bound is PSPACE. Why? In the classical case, because Nature somehow has to find a fixed point (i.e., an invariant probability distribution) of the transformation you effect from input bits to output bits, and that turns out to be a PSPACE-complete problem.

    ReplyDelete
  19. Isn't there also the factor that you need to know how far to go in time, needing some amount to space/time to compute the time distance?

    ReplyDelete
  20. Isn't there also the factor that you need to know how far to go in time, needing some amount to space/time to compute the time distance?

    Yes, but just like with ordinary Turing machines, that problem can be trivially solved by choosing any polynomial upper bound on the running time.

    ReplyDelete
  21. Too cool... I've actually had the same idea floating around my head for a couple of years now but I've been calling it "Temporal Information Services".

    The Temporal Processor I had thought up is essentially the same TTCs Grote arrived at which are driven off a micro-wormhole and allow for the instantaneous computation of complex problems.

    There's actually a second component to this technology that I call Temporal Transmitters which allow for the insteantaneous transmition of information from point A to B.

    The idea behind Temporal Transmitters is that if you need to send a message to point B that's 1 light year away you should have started sending it 1 year ago. Temporal Transmitters open the same micro-wormhole to do just that.

    What's interesting is that you only need the temporal technology on the transmission side. The receiver can be any old receiver unless you want to facilitate 2-way communication.

    In practice such technology would likely be setup in trunking networks that work much like VOIP trunks work today. Callers would connect to their local trunk and to all parties things would seem like a local call even though the parties might span extream distances...

    -Steve

    ReplyDelete
  22. Hey, just on a lighter note guys, I saw a great t-shirt recently which said:
    "Abusing time travel since 2068"

    it made me laugh.

    Time travel will no longer be a dream one day - just shame we won't be around to see it!

    ReplyDelete