2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.