# 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:

• "different resources state it differently". What resource does not agree with you about $H_1$? Aug 24 at 15:04
• 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 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.