# How to prove a problem is EXP hard

Summary of the problem: Given an alternating time turing machine ($$M$$), a polynomial $$p(.)$$ and a string ($$w$$), is it EXPhard to find if $$M$$ accepts $$w$$ using not more than $$p(|M|+|w|)$$ space?

My work: I have a problem I would like to prove is EXPTIME hard. I have a couple of reductions to do so. One is reduction from combinatorial EXP complete games but is hard to read.

The other is a reduction from alternate poly space Turing machine. But instead of taking as input a turing machine ($$M$$) and a string ($$w$$) to check for acceptance, it takes as input a turing machine ($$M$$), a string ($$w$$) and a polynomial $$p(.)$$ which gives the amount of space the turing machine is allowed to use. Is this reasonable to do?

Possible solution: Ideally I would like to write a reduction from an exphard problem to alternate turing machine with a polynomial and string. to prove that this problem is hard as well.

• What do you mean by "alternating time"? What time has to do with alternation? Commented Jul 16 at 11:56

This is an immediate consequence of the fact that $$\text{APSPACE} = \text{EXPTIME}$$ (see, for example, here). Specifically, consider a language in $$L \in \text{EXPTIME}$$, and let $$T$$ be an alternating TM that decides $$L$$ in space $$s(n)$$, where $$s:\mathbb{N} \to \mathbb{N}$$ is some polynomial. Then, a reduction from $$L$$ to your problem operates as follows. Given input $$x$$ for the reduction, the reduction outputs $$\langle T, x, s(|x|)\rangle$$. As $$T$$ decides $$L$$ with space-complexity $$s(n)$$, it holds that $$x\in L$$ iff $$T$$ accepts $$x$$ while using at most $$s(|x|)$$ tape-cells.
Note that $$T$$ is a constant (does not depend on the input $$x$$). Therefore, the reduction is computable in polynomial-time as it simply outputs the description of $$T$$, copies $$x$$, and computes $$s(|x|)$$.