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.
Saturday, June 10, 2006
Time-Travel Circuits
From Computing Like Gods
by Jörn Grote
Subscribe to:
Post Comments (Atom)
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.
ReplyDeleteBecause 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.
Er, I meant polynomial, not linear time.
ReplyDeleteShould we be impressed? Is there any science fiction where the writing is even halfway decent?
ReplyDeleteShould we be impressed? Is there any science fiction where the writing is even halfway decent?
ReplyDeleteNicholson Baker. Kurt Vonnegut. Philip K. Dick. Orson Scott Card.
I rest my case.
Macneil,
ReplyDeleteHow did you learn so much about this math?
Is there any science fiction where the writing is even halfway decent?
ReplyDeleteCounterquestion: 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.
Counterquestion: Is there any non-SF worth reading?
ReplyDeleteUhh... 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."
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.
ReplyDeleteStross 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.
In Stross's story "Antibodies" a proof for P=PN is discovered and triggers the emergence of AI among other things.
ReplyDeleteCrater.
ReplyDeleteCalcutta.
(thinks for a while)
never mind!
Isn't time travel (to the future and back) implies that any recursive function can be computed in constant time? :)
ReplyDeleteI'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."
ReplyDeleteNot to mention the one in the following paragraph. Thank god we can travel back in time and correct it!
-ff
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.
ReplyDelete"In the 23rd century, we don't need editors!"
More subtly, but perhaps more disturbring to read, are the awkward shifts into and out of the pluperfect.
ReplyDelete
ReplyDeleteNo. 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?
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?
ReplyDeleteToo 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".
ReplyDeleteThe 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
Hey, just on a lighter note guys, I saw a great t-shirt recently which said:
ReplyDelete"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!