This 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.