0
$\begingroup$

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?

$\endgroup$
7
  • 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$ Aug 27, 2017 at 10:29
  • $\begingroup$ @DavidRicherby, space hierarchy theorem doesn't apply here. $L \in PSPACE$ but not $PSPSACE-complete$ $\endgroup$
    – Logic
    Aug 27, 2017 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$ Aug 27, 2017 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$ Aug 27, 2017 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, 2017 at 10:56

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
2
  • $\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$ Aug 27, 2017 at 16:30
  • $\begingroup$ You are right, I revised my answer. Thank you. (Used to space constructible functions :) ) $\endgroup$
    – nadir
    Aug 27, 2017 at 17:28

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.