computer science - Constructing hard inputs for the complement of bounded halting

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^trangle$
let$langle N', x'rangle = CONSTRUCT(M')$
if$N = N'$and$x=x'$then output 1; that is, let$M'(langle N,x,1^trangle)=1$
else, let$y = M(langle N, x, 1^trangle)$
output$y$; that is, let$M'(langle N,x,1^trangle)= 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.

• Next nt.number theory - Irreducible polynomials with constrained coefficients
• Previous mp.mathematical physics - Applications of Euler-Cauchy ODEs