# Are subsets of $PSPACE$ closed under common operations

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.

• $SPACE(n^k)$ is not closed under $p$-time reduction by padding technique. Oct 11, 2018 at 12:50

$$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.
• In this question, the OP briefly summarize the proof of non-closedness of $SPACE(n)$ under Karp reduction. Oct 11, 2018 at 14:54