# Are run time bounds in P decidable when the problem is promised that an input program must halt?

I'm solving Problem 11-10(b) in "what can be computed".

11.10 Consider the decision problem HALTSINSOMEPOLY (HISP), defined as follows. The input is a program P, and the solution is “yes” if and only if there exists some polynomial q(n) such that, for every n, P halts after at most q(n) steps on all inputs of length ≤ n.

(a) State, with proof, which of the following statements are true: (i) HISP is undecidable, (ii) HISP ∈ Expo, (iii) HISP ∈ Poly.

(b) Would your answer to a change if we restrict the domain of HISP, so that the input P is guaranteed to halt on all inputs? (Note: This is an example of a promise problem, in which the input is promised to have a certain property, which may itself be undecidable.)

The proof of 11-10(a) is basically same as "Are runtime bounds in P decidable?", which is that HISP reduces to halting problem.

If an input program is promised to halt, however, this reduction does not help us.

Is there any suggestion to solve this problem?

Given a Turing machine $$T$$, construct a new Turing machine $$T'$$ which, in input of length $$n$$, simulates $$T$$ for up to $$n$$ steps. If $$T$$ halts then $$T'$$ also halts, and otherwise $$T$$ counts up to $$2^n$$ and then halts.
• The Turing machine $T$ is not guaranteed to halt. It is $T’$ which is guaranteed to halt. – Yuval Filmus May 15 at 6:01