I could try to argue that quantum gravity, since it does not yet really exist, might permit such things… but closed time-like curves arguably lead to inconsistencies (grandfather paradox), and any complete theory should be consistent (even if incomplete).

Not that I have any real objections to looking at fun ‘what if’ scenarios.

]]>A. Shiekh: I’m certainly not! My best guess would be that CTCs don’t exist, but that to understand why we’ll need to wait for a quantum theory of gravity. Using our best *current* theories—GR and QM—one can’t really exclude CTCs, and indeed if spacetime geometry is fluctuating quantum-mechanically, then it’s somewhat hard to understand why CTCs *shouldn’t* form. For that reason alone, I think it’s interesting to ask what the computational implications would be if CTCs existed. (The fact that the question turns out to have a clear nontrivial answer is just an added bonus.) After all, theoretical computer scientists already profitably study hundreds of computational models that are even *less* rooted in known physics! đź™‚

There is no other possibility, but this is not what

DTIME(superpoly f)âŠ†NTIME(n^(k+c)) means.

What the above inclusion means, is that there is a superpolynomial function f, such that ALL languages that can be decided by a deterministic Turing Machine in a time asymptotically less than or equal to f, can be decided by a nondeterministic Turing Machine in time n^(k+c).

To give an example, suppose k=100, c=5, and f(n) = n^(lg n). The above inclusion would mean that for every language that can be decided in n^(lg n) deterministically, there would be a non deterministic Turing Machine that could decide it in n^105.

By contrast, what you are saying is that if there is a problem that lies in NTIME(n^k+c) but not in NTIME(n^k),

and assuming PâŠ†NTIME(n^k) then any deterministic procedure would take superpolynomial time to decide this problem, which is true, but not equivalent to

DTIME(superpoly f)âŠ†NTIME(n^(k+c))

I thought it would automatically imply that P != NP because if it’s shown that PâŠ†NTIME(n^k) then either:

1. All NP-Complete problems are also in NTIME(n^k). In this case any proof that P=NP says that PâŠ†**D**TIME(n^k), which isn’t true.

2. Some or all NP-Complete problems are outside NTIME(n^k) and so P != NP.