Question

Show that PSPACE is closed under the operations union, complementation, and star.

Short answer

The entire running time is $O\left(n^{k+1}\right)$. This means that $M$ is a nondeterministic poly-time decider for${L_1}^{*}$.

Step-by-step solution

To PSPACE the collection

PSPACE is the collection of all decision problems that a Turing machine can answer using a polynomial space in computational complexity theory. If we denote by $SPACE\left(f\left(n\right)\right)$, the set of all problems that can be solved by turning machines using $O\left(t\left(n\right)\right)$ space for some function t of the input size n, then we can define PSPACE formally as

$PSPACE=\underset{k\in N}{\cup }SPACE\left(n^k\right)$

PSPACE is a strict superset of the set of context-sensitive languages.

To explain the nondeterministic function

Suppose that $L_1,L_2\in NP$. This means that there exist nondeterministic deciders $M_1$and $M_2$that decide $L_1$in nondeterministic time and in nondeterministic time $O\left(n^k\right)$and $L_2$in nondeterministic time $O\left(n^l\right)$, respectively.

It is possible to demonstrate that

1. There is a poly-time decider$M$that is nondeterministic and can be given as $L\left(M\right)=L_1\cap L_2$.
2. There is a poly-time decider $M$that is nondeterministic and can be given as $L\left(M\right)=L_1\cup L_2$, and
3. There is a poly-time decider $M$ that is nondeterministic and can be given as role="math" localid="1663221411071" $L\left(M\right)=L_1\circ L_2$, and
4. There is a poly-time decider $M$that is nondeterministic and can be given as $L\left(M\right)={L_1}^{*}$.

To Set up the four machines

Now, set up the four machines $M$for the various operations. The structures are typical; the complexity analysis of the running time is an added feature. It's worth noting that it can simplify the constructs by leveraging the power of nondeterministic options.

1. Intersection:

M=”On input :

1. Execute $M_1$on $w$. If $M_1$is rejected, then reject.
2. Otherwise, execute $M_2$on $w$. If rejected then reject.
3. Else accept.”
4. Union:

M=”On input $w$:

1. Execute $M_1$on $w$. If $M_1$is rejected, then reject.
2. Otherwise, execute $M_2$ on $w$. If rejected then reject.
3. Else accept.”

Clearly, in every computation tree on input $w$of length $n$, the longest branch is $O\left(n^{\max \{k,l\}}\right)$. As a result, $M$ is a nondeterministic poly-time decider for $L_1\cap L_2$.

Note that we are not running $M_1$and $M_2$in parallel in the preceding situations, as this was required in the proof that identifiable languages are closed under union. Another option is to choose either $M_1$ or $M_2$in a nondeterministic manner and then simulate only that machine.

To Concatenation the input states

1. Concatenation:

M = ”On input :

1. Split $w$into $w_1,w_2$in a nondeterministic way so that $w=w_1,w_2$.
2. Execute $M_1$ on role="math" localid="1663222239526" $w$. If $M_1$ is rejected, then reject.
3. Otherwise, execute role="math" localid="1663222276819" $M_2$on w. If $M_2$rejected then reject.
4. Else accept.”

Clearly, in every computation tree on input w of length n, the longest branch is $O\left(n^{\max \{k,l\}}\right)$. Because on a two-tape TM, step 1 requires just $O\left(n\right)$ steps. As a result, $M$is a nondeterministic poly-time decider for$L_1\circ L_2$.

1. Kleene star:

M = ”On input :

1. Accept if it is a $w=\in$.
2. Select a number $m$in a nondeterministic manner such that $1\le m\le \left|w\right|$.
3. Split nondeterministicallyrole="math" localid="1663222498881" $w$ into$m$ pieces in such a way that$w=w_1{w}_2...w_m$
4. For all $i,1\le i\le m;$: Execute $M_1$on $w$. If$M_1$is rejected, then reject.
5. Else ( $M_1$accepted all $w_i,1\le i\le m$), accept”.