0
$\begingroup$

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:

Update: wiki exp-complete article now updated to describe H1

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Aug 22 at 21:40
  • $\begingroup$ @D.W. - I updated accordingly, thank you! $\endgroup$
    – gfunk
    Aug 24 at 13:56
  • $\begingroup$ "different resources state it differently". What resource does not agree with you about $H_1$? $\endgroup$
    – Steven
    Aug 24 at 15:04
  • $\begingroup$ @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). $\endgroup$
    – gfunk
    Aug 24 at 15:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bernardo Subercaseaux
    Aug 25 at 14:53

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I think this is correct. Many resources confirm H1 complexity is EXP-Complete. Wikipedia article implying H2's complexity as EXP-Complete is likely miswording / intended to reference H1. Will mark as answer if StackExchange community review does not disagree in next week. Thanks. Update wikipedia article cites this which is indeed H1 $\endgroup$
    – gfunk
    Aug 28 at 17:28

Your Answer

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

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