# Discrepancy in Time-Complexity of Bounded Halting Problem

Can you please help identify if the two following variants of the bounded halting problem are in different deterministic complexity classes?

$$H1 = \{ (\langle M \rangle, w, t) \mid \text{M accepts w in time at most t} \}$$ $$H2 = \{ (\langle M \rangle, t) \mid \forall \text{w, M accepts w in time at most t} \}$$ $$\text{(where t is binary-encoded for both)}$$ When I do the math, (ignoring simulation cost for readability), I get:

• $$H1 = O(2^{N}) \in$$ EXP-TIME
• $$H2 = O(2^{N})*O(2^{2^N}) \in$$ 2-EXPTIME
• To illustrate my thinking, here are a few examples:
t (base 10) t (base 2) N H1 (Single Simulation) Total Unique inputs length t H2
2 10 2 2 steps = O(2^N) 4 = O(2^(2^N)) 8 = 4*2
3 11 2 3 steps 8 16 = 8*3
4 100 3 4 steps 16 48 = 16*3
9 1001 4 9 steps 512 2048 = 512*4

Resources regarding H2:

Resources for H1:

• Please ask only one question per post. Rather than asking about multiple problems, it is best to ask about only one. Since you want to ask about two problems, you could ask about each separately in a separate question. By the way, the name of this site is CS Stackexchange, not CS Stackoverflow.
– D.W.
Aug 22, 2023 at 21:40
• @D.W. - I updated accordingly, thank you! Aug 24, 2023 at 13:56
• "different resources state it differently". What resource does not agree with you about $H_1$? Aug 24, 2023 at 15:04
• @Steven - non disagree about H1 (nor do I), but some state "h2 is exp-complete", which i do not believe. (fwiw, my original question was what are the complexities of h1 and h2, respectively. I was asked to update to be a singular question, so i reworded to "whats the difference btwn the two" - sorry for confusion). Aug 24, 2023 at 15:23
• could you give a complete list of the "some"? As my current answer is saying, I think the Wikipedia case might be just an issue with the wording, rather than a mathematical discrepancy. But if you have some other sources saying more explicitly that $H_2$ is in EXP that would be quite interesting; I don't have a concrete argument to rule it out, but I believe $H_2 \in \text{EXP}$ to be a very unlikely statement. Aug 25, 2023 at 14:53

I think it's simply that the Wikipedia page is a bit sloppy as it seems to be referring to $$H_1$$ (based on the text), even though I agree with you in that it could read as if it was talking about $$H_2$$. It is indeed true that $$H_1$$ is EXP-complete. About the status of $$H_2$$, I would also guess 2EXP-completeness, but the only obvious part is membership.