0
$\begingroup$

By "subsets of $PSPACE$" I am referring to classes like $SPACE(n^k)$ for some constant $k$ (e.g. $k = 42$).

Under the union, intersection, and concatenation operations, such subset is apparently closed.

For the Kleene star and polynomial-time reduction, I am not so sure. Here's what I have tried:

  1. To show that $PSPACE$ is closed under Kleene star, assume that some $L \in PSPACE$. To decide whether some input $w \in L^*$, we can non-deterministically split the $w$ into $i$ chunks ($1 \leq i \leq n$, and $i$ is chosen non-deterministically), and check if each chunk is in $L$. If that check can be done in $O(n^k)$ space, this whole procedure can be done in $NSPACE(n^k) \subset SPACE(n^{2k}) \subset PSPACE$ (the first inclusion is by Savitch's theorem). In a similar manner, I tried to show that a subset like $SPACE(n^k)$ is NOT closed because $2k > k$.

  2. To show that $PSPACE$ is closed under polynomial time reduction, suppose some $L_2 \in PSPACE$ and some $L_1 \leq_p L_2$. Since the reduction is in polynomial time, it uses at most polynomial space, so $L_1 \in PSPACE$. I tried to show that something like $SPACE(n^k)$ is NOT closed under polynomial time reduction by saying that the reduction might runs in $O(n^j)$ time and $j > k$, then the whole process will use at most $O(n^j)$ space, which is no longer in $SPACE(n^k)$.

My doubts:

  1. For the Kleene star closure proof, we can't guarantee that deciding $L^*$ will necessarily use $O(n^{2k})$ space, since we don't have $NSPACE(n^k) = SPACE(n^{2k})$.

  2. For the polynomial time reduction closure proof, such a $O(n^j)$ space reduction exists, but it might not actually uses more than $O(n^k)$ space.

I can't really convince myself one way or the other, so any help is appreciated.

$\endgroup$
  • $\begingroup$ $SPACE(n^k)$ is not closed under $p$-time reduction by padding technique. $\endgroup$ – Thinh D. Nguyen Oct 11 '18 at 12:50
1
$\begingroup$

$SPACE(n^k)$ is closed under Kleene star. Just enumerating all possible partition (which can be done in linear space, or at most quadratic or $nlogn$ space), then decide each partition using the $n^k$-space machine.

This class is not closed under poly-time reduction. Prove by padding technique. This part would be found here at CS.SE or CSTheory.SE

$\endgroup$
  • $\begingroup$ Thanks for the answer! I'm not very well versed with this, so could you please elaborate a bit? For the polynomial time reduction, I've tried to search for "padding" and "space padding" on both sites, but I've only found mentions of some padding argument. I've checked the Wikipedia page of that, but I don't see how is that related. $\endgroup$ – user869887 Oct 11 '18 at 13:12
  • $\begingroup$ Theoretical Computer Science SE is only for research-level questions so this wouldn't be on-topic there. $\endgroup$ – David Richerby Oct 11 '18 at 13:16
  • 1
    $\begingroup$ In this question, the OP briefly summarize the proof of non-closedness of $SPACE(n)$ under Karp reduction. $\endgroup$ – Thinh D. Nguyen Oct 11 '18 at 14:54
  • $\begingroup$ @ThinhD.Nguyen I see. One last question: is there any other technique to prove this? Just curious about other possibilities. $\endgroup$ – user869887 Oct 11 '18 at 23:59

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.