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?


1 Answer 1


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.

  • $\begingroup$ Thank you for your comment! When we don't know whether a Turing machine T halts or not, we can reduce HISP to halting-problem as you did(which corresponds to 11-10(a)). My Question is about 11-10(b). is HISP decidable if the problem guarantees that the Turing machine T halts, and what is the computation complexity? Since the Turing machine T halts, (I think) halting-problem is decidable , and we could not show the undecidabllity of HISP using your reduction. If I have a misunderstand, I would appreciate it if you could correct it. $\endgroup$
    – yoshi
    May 15, 2021 at 3:35
  • $\begingroup$ I gave a reduction from the halting problem to the language in 11-10(b). $\endgroup$ May 15, 2021 at 4:15
  • $\begingroup$ Sorry, I miswrite the direction of the reduction, but my question is same. When the Turing Machine T is guaranteed to halt, the halting problem is decidable(because T is guaranteed to halt). So (I think) we could not use this reduction to show the undecidablity of HISP. $\endgroup$
    – yoshi
    May 15, 2021 at 4:28
  • $\begingroup$ The Turing machine $T$ is not guaranteed to halt. It is $T’$ which is guaranteed to halt. $\endgroup$ May 15, 2021 at 6:01
  • $\begingroup$ Wow, I understand it! Thank you so much! $\endgroup$
    – yoshi
    May 15, 2021 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.