4
$\begingroup$

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/

Improve this question
$\endgroup$
5
  • $\begingroup$ Can you define "constructed" more precisely? E.g. are there time constraints on the construction? $\endgroup$
    – Ryan Williams
    Commented Aug 27, 2010 at 1:27
  • $\begingroup$ The time constraint on construction is preferably polynomial time. $\endgroup$
    – Hunter Monroe
    Commented Sep 7, 2010 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
    Commented Apr 20, 2014 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
    Commented Sep 29, 2014 at 2:43
  • 1
    $\begingroup$ OK, this is more clear now; thanks for the edit! $\endgroup$
    – Joel David Hamkins
    Commented Sep 29, 2014 at 13:48

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .