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

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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.