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.

New contributor
user869887 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • $SPACE(n^k)$ is not closed under $p$-time reduction by padding technique. – Thinh D. Nguyen Oct 11 at 12:50
up vote 2 down vote accepted

$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

  • 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. – user869887 Oct 11 at 13:12
  • Theoretical Computer Science SE is only for research-level questions so this wouldn't be on-topic there. – David Richerby Oct 11 at 13:16
  • In this question, the OP briefly summarize the proof of non-closedness of $SPACE(n)$ under Karp reduction. – Thinh D. Nguyen Oct 11 at 14:54
  • @ThinhD.Nguyen I see. One last question: is there any other technique to prove this? Just curious about other possibilities. – user869887 Oct 11 at 23:59

Your Answer

user869887 is a new contributor. Be nice, and check out our Code of Conduct.
 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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