-2
$\begingroup$

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...

$\endgroup$
4
  • 1
    $\begingroup$ Can you pick one result you want to know about? We discourage asking multiple questions in a single post; usually it is better to post each one separately. Also, what have you tried? What approaches have you already considered for proving it? Where are you stuck? $\endgroup$
    – D.W.
    Commented Mar 7, 2019 at 5:26
  • $\begingroup$ Please see the updated description. $\endgroup$ Commented Mar 7, 2019 at 7:06
  • 3
    $\begingroup$ If you can show that P is closed under complement, exactly the same proof shows that any deterministic class is closed under complement. If you can't see how to do that, it suggests that your closure proof for P is more complicated than it needs to be. It's basically one sentence. $\endgroup$ Commented Mar 7, 2019 at 11:24
  • $\begingroup$ I've rolled this back; please don't wipe the content out of a question after it's been answered. There's no real benefit to it, and it means it can't help anyone who searches for it in the future. $\endgroup$
    – Draconis
    Commented Mar 8, 2019 at 3:00

1 Answer 1

2
$\begingroup$

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 PSPACE.

$\endgroup$
2
  • $\begingroup$ That constant really ought to be zero! All you need to do is swap the accepting and rejecting states in the original TM... $\endgroup$ Commented Mar 7, 2019 at 21:18
  • $\begingroup$ @DavidRicherby True, but adding the overhead of "look at the result and return true or false" (requiring one bit of space) seemed easier to explain than "swap which states accept and reject". $\endgroup$
    – Draconis
    Commented Mar 7, 2019 at 21:33

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