How would you prove PSPACE is closed under union? So far, my thought process is that we can create an algorithm to show that P is closed under union. I'm struggling with how I can connect that to PSPACE...

  • $\begingroup$ Perhaps I'm being rather pedantic, but you should probably make it explicit you mean finite union. In this case, you only really need to prove $P_1, P_2 \in \textbf{PSPACE}$ implies $P_1 \cup P_2 \in \textbf{PSPACE}$ (i.e., union of two sets, not arbitrarily many). Given (poly-space) algorithms $A_1$ for $P_1$ and $A_2$ for $P_2$, how would you check if an input is in $P_1 \cup P_2$? $\endgroup$ – dkaeae Mar 7 '19 at 8:21
  • 1
    $\begingroup$ Essentially the same proof works for any complexity class, so I'm not sure what your problem is, here. $\endgroup$ – David Richerby Mar 7 '19 at 11:26
  • $\begingroup$ @dkaeae "Finite" is strongly implied. Almost everything we do in computer science is finitary. (Not least because making most things infinite -- e.g., taking infinitary unions, allowing infinitely many states in an automaton, etc. -- makes them trivially able to do everything, which isn't at all interesting.) $\endgroup$ – David Richerby Mar 7 '19 at 11:28

(First, I'm assuming you mean finite union, not infinite union. As dkaeae points out in the comments, this is an important distinction!)

Let's say you have languages $P_0, P_1, \cdots P_n$, which are all in PSPACE. In other words, there exist Turing machines $T_0, T_1, \cdots T_n$ which decide (using polynomial space) whether a given input is in $P_0, P_1, \cdots P_n$ respectively.

Now you have an input $x$ and want to decide if it's in $P_0 \cup P_1 \cup \cdots \cup P_n$. The algorithm for this is straightforward: run $T_0(x), T_1(x),$ and so on, in order. If any of these machines accepts, then $x$ is in the union. If none of them accepts, $x$ is not in the union.

The space required is the maximum of the space taken by each Turing machine. Since each Turing machine takes polynomial space, the largest must be polynomial. Therefore the union is in PSPACE.

  • $\begingroup$ @Apass.Jack Mostly it seemed redundant, since David had already said it :P $\endgroup$ – Draconis Mar 22 '19 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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