[Computational Complexity] 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.
Posted by Lance to Computational Complexity at 6/10/2006 05:23:00 PM