If there is always a hard input for the complement of bounded halting, can that input be constructed?

More precisely, suppose that

for any deterministic TM $M$ accepting $$ \text{coBHP}=\{\langle N,x,1^t\rangle\mid \text{ nondeterministic TM N does not halt on input x within t steps}\}, $$ there exists some non-halting $\langle N',x'\rangle$ such that the function $f(t)=T_M(N',x',1^t)$ is not bounded by any polynomial.

In that case, given $M$, can $\langle N',x'\rangle$ be constructed by a polynomial time deterministic TM?

For background, see http://eccc.hpi-web.de/report/2009/056/

  • $\begingroup$ Can you define "constructed" more precisely? E.g. are there time constraints on the construction? $\endgroup$ – Ryan Williams Aug 27 '10 at 1:27
  • $\begingroup$ The time constraint on construction is preferably polynomial time. $\endgroup$ – Hunter Monroe Sep 7 '10 at 17:55
  • 1
    $\begingroup$ I am confused by a few things. When the OP speaks of $f$ being bounded by a polynomial, is he or she referring to the running time of program $M$ on that input? The function $f$ itself appears to map the input to accept/reject. Also, is the polynomial bound now meant to be polynomial in $t$ (as he wrote $t$ in unary), or in $|t|$ (non-unary)? If the former, then the boxed assumption seems just false, since $M$ could simply simulate $N$ on $x$ for $t$ steps, and the run time of this is linear in $t$. $\endgroup$ – Joel David Hamkins Apr 20 '14 at 23:30
  • $\begingroup$ Joel, I edited the problem to change "NTM" to "nondeterministic TM". Then, the run time of M simulating N on x for t steps is not linear unless P=NP. $\endgroup$ – Hunter Monroe Sep 29 '14 at 2:43
  • 1
    $\begingroup$ OK, this is more clear now; thanks for the edit! $\endgroup$ – Joel David Hamkins Sep 29 '14 at 13:48

No, such $\langle N', x'\rangle$ is not constructible at all given only a description of $M$, even if you remove the requirement of polynomial time.

Suppose that $CONSTRUCT$ is such a deterministic turing machine outputting $\langle N', x'\rangle$. Note that by your requirement, $N'$ must never halt on input $x'$, no matter how much time $N'$ is allowed to run.

Let $M$ be your favorite deterministic turing machine accepting $\text{coBHP}$. Write a new machine $M'$ as follows:

Input$\langle N, x, 1^t\rangle$ let$\langle N', x'\rangle = CONSTRUCT(M')$ if$N = N'$and$x=x'$then output 1; that is, let$M'(\langle N,x,1^t\rangle)=1$ else, let$y = M(\langle N, x, 1^t\rangle)$ output$y$; that is, let$M'(\langle N,x,1^t\rangle)= y$

That is, $M'$ uses Kleene's recursion theorem to construct a hard input for itself and uses the fact that $CONSTRUCT$ outputs never-halting machines to make that 'hard' input very easy (actually, now bounded by a constant), which is a contradiction. Therefore, $CONSTRUCT$ cannot exist.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.