# Is there a non PSPACE language s.t exponential padding of it is PSPACE?

I've had an exam in computational models a few days ago, and would like to check whether I made a mistake. The question goes like that:

Is there a language $$L \notin PSPACE$$ over the alphabet {0,1} such that $$L_{pad} = \{wp^{2^{|w|}-|w|} | w \in L\} \in PSPACE$$ over tha alphabet {0,1,p}.

On the spot I answered no, because L is poly-space reducible to $$L_{pad}$$ so that would contradict $$L \notin PSPACE$$. I also wrote that a poly-space reduction works because I don't have to write the full reduction result in order to use it, just re-calculate it whenever I need the i'th letter of the result.

In retrospect I think I may be wrong, because padding allows me to use space exponential in |w| while staying polynomial in terms of the padded w length.

Both of these answers seem intuitively reasonable, and I would like your help determining which one is correct and why the other one isn't.

Thanks

Yes, there are such languages. Consider a language $$L$$ that is in e.g., $$SPACE[2^{n/2}]$$, but not in PSPACE. Such a language exists by the space hierarchy theorem.
I claim $$L_{pad}\in PSPACE$$. Indeed, given input $$wp^k$$, it's first easy to verify in PSPACE that $$k=2^{|w|}$$, by simply computing the length of $$w$$. Then, it can be decided whether $$w\in L$$ using $$O(2^{n/2})$$ space, which is less than $$2^k$$ for any large enough $$k$$.
The point is that the addition $$p^{2^{|w|}}$$ provides you with "free" computation time/space.