3 ms·
www.scottaaronson.com/papers/ctc.pdf Shows that (with or without quantum computing) you can do all of PSPACE using a CTC (in polynomial time) and no more.
by tjhance 12y ago
www.scottaaronson.com/papers/ctc.pdf
Shows that (with or without quantum computing) you can do all of PSPACE using a CTC (in polynomial time) and no more.
- mshron 12y agoThis is the key result in this conversation; this should be higher. Basically: if we insists on Deutsch's causal fixed point propety of CTCs, they do not give you P=NP, they give you P=PSPACE. That is, all problems which can be solved in polynomial space can now be solved in polynomial time, and vice versa. So for a time-travel computer to give P=NP or P=O(1), it would have to violate Deutsch's causality criterion. I have almost zero knowledge of either field, but it sounds to me like it makes Deutsch's model more plausible.
- evanb 12y agoPSPACE is bigger than and contains NP. You still don't get ANYTHING=O(1), though. https://en.wikipedia.org/wiki/NP_(complexity)#Relationship_to_other_classes https://en.wikipedia.org/wiki/NP_(complexity)#Relationship_t...