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$
1
  • $\begingroup$ $SPACE(n^k)$ is not closed under $p$-time reduction by padding technique. $\endgroup$ Oct 11, 2018 at 12:50

1 Answer 1

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$
4
  • $\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, 2018 at 13:12
  • $\begingroup$ Theoretical Computer Science SE is only for research-level questions so this wouldn't be on-topic there. $\endgroup$ Oct 11, 2018 at 13:16
  • 1
    $\begingroup$ In this question, the OP briefly summarize the proof of non-closedness of $SPACE(n)$ under Karp reduction. $\endgroup$ Oct 11, 2018 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, 2018 at 23:59

Your Answer

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

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