The Wikipedia article on the Novikov self-consistency principle has a section on time loop logic, where it discusses using time travel to solve any NP problem by finding an algorithm where the only consistent outcome is the solution.
For example you could have an algorithm as follows:
To find a factor of a number $n$:
If you receive a message from the future with a number y, and y is a factor of n, set x = y
If you receive a message from the future with a number y, and y is not a factor of n, set x = (y + 1) mod n
If you receive no message from the future, or an invalid message, set x = 1
After 1 hour send x back into the past.
The only self consistent outcome is that you immediately receive a message from the future with a factor of n.
But couldn't you use this same technique to create a scenario where there are no possible consistent outcomes? E.g. always send back a different number to the one you received?
Ergo there must be some reason why this setup isn't possible. In which case why do we assume it would work for problems that do have a consistent outcome?