# 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 $M$ accepting coBHP={$\langle N,x,1^t\rangle|\langle N,x,1^t\rangle \text{ NTM 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 N,x be constructed?

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

-
Can you define "constructed" more precisely? E.g. are there time constraints on the construction? –  Ryan Williams Aug 27 '10 at 1:27
The time constraint on construction is preferably polynomial time. –  Hunter Monroe Sep 7 '10 at 17:55