Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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/

share|improve this question
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
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$. –  Joel David Hamkins Apr 20 at 23:30
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. –  Hunter Monroe Sep 29 at 2:43
OK, this is more clear now; thanks for the edit! –  Joel David Hamkins Sep 29 at 13:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.