3 ms·
Is there any math addressing how much more quickly NP-hard problems could be computed when time is a flat circle?
by debt 10y ago
Is there any math addressing how much more quickly NP-hard problems could be computed when time is a flat circle?
- gjm11 10y agoYup, or at least when you have access to a "closed timelike curve" which I think is close enough to what you're asking. See, e.g., this -- which is a transcript of a lecture given by the author of the survey article in the OP. http://www.scottaaronson.com/democritus/lec19.html http://www.scottaaronson.com/democritus/lec19.html With the help of a CTC you can solve any problem in class NP in polynomial time; in fact you can do better and solve anything in PSPACE in polynomial time; and the capabilities of quantum and classical computers are the same. (The last of those is a result due to Scott Aaronson -- author of the survey article in the OP -- and John Watrous.)