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:


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 &gt; k$.
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 &gt; k$, then the whole process will use at most $O(n^j)$ space, which is no longer in $SPACE(n^k)$.


My doubts:


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