I am currently working on proving that the bounded halting problem is $EXP$-Complete. The bounded halting problem is defined by the language $L$ as follows:

$$L = \{\langle M,x,t \rangle : \text{determenstic TM }M \text{ halts on }x \text{ after at most }t \text{ steps}\}$$

I have successfully shown that this language is in $EXP$. However, I am facing some challenges in proving that it is $EXP$-Complete using polynomial reduction $L' \leq_p L$ for any $L' \in EXP$.

Interestingly, I have found it easier to prove the $EXP$-Completeness for the language:

$$A = \{\langle M,x,t \rangle : \text{determenstic TM }M \text{ accepts }x \text{ after at most }t \text{ steps}\}$$

Please note that the last language is the bounded accept problem and not the same as the one defined earlier.

The proof states that for any input $y$ for $L'$, we can build an instance of $A$ as required and answer the same as $A$ does.

However, I have come to realize that this proof is not valid for $L$ since if I attempt to do the same, then for an input $y$ that $L'$ rejects (i.e., its Turing machine halts and rejects it), the Turing machine of $L$ will still accept it since it halts on it.

I would greatly appreciate any guidance or assistance you can offer to help me refine my proof for the $EXP$-Completeness of $L$. Thank you for your time and consideration.

  • $\begingroup$ Think of a reduction from bounded accept to bounded halt $\endgroup$ Jul 23, 2023 at 17:37
  • $\begingroup$ @CommandMaster To be honest I thought of such an approach but I don't want it to be like this. If I'm following this approach I have to prove that bounded accept is also in EXP. I'm sure a refinement could be done with the proof I provided in the question. $\endgroup$
    – Straw User
    Jul 23, 2023 at 17:44
  • $\begingroup$ (1st symbols)... t is some number of steps, <t> is t encoded/written in binary, |<t>| is the length of <t>. (2nd math)… ceiling( log_base2(t)) = |<t>| thus 2^|<t>| = t. (3rd proof statement)… the math says the input length is a log of the maximum number steps that may need to be simulated. - ie verification steps grow exponentially compared to input size. Not 100% ther but hopefully helps. $\endgroup$
    – gfunk
    Oct 11, 2023 at 2:52
  • $\begingroup$ Some proofs for A is EXP-COMPLETE in references of this question cs.stackexchange.com/questions/161725/… $\endgroup$
    – gfunk
    Oct 11, 2023 at 3:17


Your Answer

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