Re:P vs. NP
by debt on Wednesday January 04, 2017 @01:51AM
(#13316209)
Is there any math addressing how much more quickly NP-hard problems could be computed when time is a flat circle?
[ Parent
| on HN ]
Yup, 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
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.)