Constructing hard inputs for the complement of bounded halting 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/
 A: 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.
