Let HALTS-IN-N be the canonical $EXPTIME$-complete language {<$M$,$n$> | the deterministic Turing machine (DTM) encoded by $M$ halts in $n$ or fewer steps, with $n$ encoded in binary}. Since HALTS-IN-N is accepted in $EXPTIME$ by simulating $M$ for $n$ steps (or until it halts, whichever comes first), its complement is also $EXPTIME$-complete just by swapping the "accept" and "reject" states.

Define the *execution trace* of a DTM to be the string of transitions its finite control goes through in the process of accepting an input.

A language is in $NP$ if each string in the language has a polynomially-sized certificate with which that string's membership in the language can be verified in polynomial time.

Now suppose $NP=EXPTIME$. Then every instance of HALTS-IN-N has a certificate that $M$ halts in $n$ steps, and this certificate has size polynomial in the size of <$M$,$n$>, which has size logarithmic in the size of $M$'s execution trace (because $n$ is encoded in binary.)

Put another way, the fact that any DTM has halted or not after $n$ steps has two witnesses: its execution trace (size $n$) and its certificate (size logarithmic in $n$).

Question 1: Is the above reasoning valid?

I think the biggest candidate for a hole in it is that I'm assuming |$M$| is essentially a constant. For a particular $M$ it is, but I don't know if it poses problems when generalizing the statement to every DTM.

Question 2 (soft): If it is valid, how surprising are the consequences?

It sounded quite surprising to me initially, but then I started looking at execution traces of Busy Beaver TM's and realized that there is a lot of redundancy in them; it's not unimaginable to me that a DTM that halts in 47 million steps could have a *proof* of that fact that is much shorter.

But this part still does seem surprising: in this scenario, you could apparently "run" a DTM not by simulating it step-by-step, but rather by searching for this logarithmically-shorter execution proof.

In fact, what prevents me from finding an execution proof in exponential time even when $M$ represents some problem known to be *outside* $EXPTIME$? I can't see it yet, but there must be something; it's inconceivable that $NP$ and $EXPTIME$ could be separated with such a simple argument!

**EDIT**: As Emil Jeřábek pointed out, I meant polylogarithmic when I wrote logarithmic (apologies for the sloppiness.) Perhaps I should also have added "(relative to the surprisingness of other known consequences of NP=EXPTIME)" to question 2.

I'll try to give a concrete example for my last paragraph. Consider a DTM that initially writes an encoding of a primitive recursive function to its tape and which then proceeds to simulate that function, reading it off the tape -- call this machine $M$. An upper bound (not tight) on the maximum running time of the function should not be difficult to discover by examining its loops -- call this $n$. Have the DTM halt immediately if the function computes some value, but have it loop $n$ more times before halting if it computes some other value. (Or use some equivalent trick to tie the result of the function to the number of steps in which the DTM halts.)

The set of such DTMs is outside $PR$ (which is known to be outside $EXPTIME$), but still in $R$, as they always halt. But such <$M$,$n$> pairs could be given as instances of HALTS-IN-N, and (under the assumption $NP=EXPTIME$) proofs that they halt or not in $n$ steps could be found in time exponential in |<$M$,$n$>|.

Is it just that $n$ is necessarily so enormous that |<$M$,$n$>| is itself enormous, so that time exponential in it is in the territory of the Ackermann function?