[FOM] Reply to Timothy Chow

[Stephen Cook]

Timothy Chow Asks:

  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.

Reply to Timothy Chow:

This question is not hard to answer, because the hierarchy theorem
has a constructive proof.

Fix some standard method of representing Turing machines by strings
and let |M| be the length of the string representing the  machine M.
It is convenient  to assume that the representation is "paddable",
meaning that for every  m greater  than |M| there is a string
of length m which also represents M.  Also we may assume that 
every string w represents some machine M, by taking M to be some fixed
trivial machine if w does not otherwise represent a machine.

Here is a language L_0 which is complete for EXPTIME such that given
(M,p) we can easily find a string x which refutes M.
Namely L_0 is the set of all strings w
such that the machine represented by w does not accept w within 2^{|w|}
steps.   Given any machine M, choose any string x representing
M such that x is long enough so that 2^{|x|} > p(|x|).  If M halts
on input x within p(|x|) steps, then M accepts x iff x is not  in L_0. 

We can use L_0 to prove a result that applies to any EXPTIME complete
(or even any EXPTIME hard) language L.  Here we can take  q(m)=m in
case L = L_0.

Theorem:  For every language L which is hard for EXPTIME there is a polynomial
q(m) such that n(M,p) is at most q(m), where m is the least k greater
than or equal to |M| such that 2^k > p(q(k)) + q(k).  Further, a refuting
string x of length q(m) can be found in time polynomial in m.

Proof: Let L be any language hard for EXPTIME.  Since L_0 is in EXPTIME, this
means that there is a polynomial time computable function f such
that for all strings w,
(*)        w is in L_0 iff f(w) is in L.
Given any machine M, let M' be a machine that on input w computes
f(w) and then acts like M on input f(w).  Let q(m) be a polynomial
such that M' computes f(w) within q(|w|) steps before acting like M.

Suppose that w represents M' and let x=f(w), and assume that
M halts on input x within p(|x|) steps.  Then M' on input w halts
within q(|w|) + p(q(|w|)) steps.  So as long as w is long enough that
     2^{|w|} > q(|w|) + p(q(|w|))
then
    (M accepts x) iff
    (M' accepts w) iff
    (w is not in L_0) iff  [by definition of L_0]
    (x is not in L)  [by (*), since x=f(w)].

Thus x refutes (M,p) with respect to L.

Stephen Cook