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?