[FOM] Complexity of refuting Turing machine impostors

[Timothy Y. Chow]

Pick your favorite EXPTIME-complete language L, and define a function n as
follows: Given any Turing machine M and any polynomial p, let n(M,p) be
the length of the shortest x that refutes M, i.e., the shortest x on which
M fails to halt with the correct answer ("x in L" or "x not in L") after
p(|x|) steps.  Such an x must exist, by the time hierarchy theorem, and
can be effectively computed by exhaustive search.

Is there anything known, or even conjectured, about the complexity or the
growth rate of n(M,p)?  Naively, I would think that there might exist
machines M that are very difficult to distinguish from machines that
correctly decide L, since without the time bound p it is undecidable
whether a given machine correctly decides L.

Of course, I picked PTIME and EXPTIME just for illustration; I am also
interested in the analogous question for any other pair of complexity
classes (uniform or not) that are provably or conjecturally separated.

Tim