# Proving EXP-Completeness for the Bounded Halting Problem

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.

• Think of a reduction from bounded accept to bounded halt Jul 23, 2023 at 17:37
• @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. Jul 23, 2023 at 17:44
• (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. Oct 11, 2023 at 2:52
• Some proofs for A is EXP-COMPLETE in references of this question cs.stackexchange.com/questions/161725/… Oct 11, 2023 at 3:17