How would you prove PSPACE is closed under complement? So far, my thought process is that we can create an algorithm to show that P is closed under complement. I'm struggling with how I can connect that to PSPACE...
Let $P$ be an arbitrary language in
PSPACE. In other words, there exists a Turing machine $T$ that decides (using polynomial space) whether an arbitrary input $x$ is in $P$.
Now we can write an algorithm to decide whether $x$ is in $\neg P$:
- Run $T$ on $x$
- If $T$ accepts, reject
- If $T$ rejects, accept
This takes however much space $T$ takes, plus a constant. A polynomial plus a constant is still a polynomial. Therefore, $\neg P$ is in