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

Question

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

Answer 1

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.