We have a language $L \in PSPACE$. Is it possible to reduce it with $f \in LOGSPACE$ to $L'$ and $L' \in DSPACE(O(1))$? Why/why not?

  • 2
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help with conceptual questions but just solving homework-style exercises for you is unlikely to really help. Look up the space hierarchy theorem. $\endgroup$ – David Richerby Aug 27 '17 at 10:29
  • $\begingroup$ @DavidRicherby, space hierarchy theorem doesn't apply here. $L \in PSPACE$ but not $PSPSACE-complete$ $\endgroup$ – Logic Aug 27 '17 at 10:31
  • 1
    $\begingroup$ It depends on the language. If $L$ is regular, for example, then it is possible, while in other circumstances it is impossible. $\endgroup$ – Yuval Filmus Aug 27 '17 at 10:35
  • $\begingroup$ @Logic The answer depends on the exact complexity of $L$. Any full answer to the question will require the space hierarchy theorem for at least one of the cases. $\endgroup$ – David Richerby Aug 27 '17 at 10:46
  • $\begingroup$ @YuvalFilmus, isn't solving a problem and outputting answer a reduction to problem of constant length? Any other machine can read the answer (using same alphabet). $\endgroup$ – rus9384 Aug 27 '17 at 10:56

The only languages in $PSPACE$ that can be reduced by the above constraint are languages in $LOG-SPACE$.

Assuming it's a Karp reduction:

A language in $DSPACE(O(1))$ is in $DTIME(O(n))$ (the number of configurations is linear). [Thanks to Yuval's comment]

Clearly, everything you can solve in $DSPACE(O(1))$ you can solve in $DSPACE(O(logn))$; So, you might as well leave a bit flag indicating whether to accept the string or not when you reduce the language by solving it in the transducer directly.

Thus, the reduction function will decide the language and since you are constrained to $LOGSPACE$ reduction you can decide only languages in $LOGSPACE$.

  • $\begingroup$ All regular languages are in $\mathsf{DSPACE}(O(1))$, but most of them are not in $\mathsf{DTIME}(O(1))$. When counting configurations, you should also count the head positions. $\endgroup$ – Yuval Filmus Aug 27 '17 at 16:30
  • $\begingroup$ You are right, I revised my answer. Thank you. (Used to space constructible functions :) ) $\endgroup$ – nadir Aug 27 '17 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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