1
$\begingroup$

Let $A,B\subsetneq\Sigma^*$ be PSPACE-complete problems for some fixed $\Sigma$ such that $A\cup B\neq\Sigma^*$ and $A\cup B\in\mathrm{PSPACE}$. Does it follow that $A\cup B$ is PSPACE-complete?


In general, is there a sufficient condition for the union of PSPACE-hard (or complete) problems to be PSPACE-hard (complete)?

$\endgroup$

1 Answer 1

4
$\begingroup$

Let $A,B\subsetneq\Sigma^*$ be $\text{PSPACE}$-complete problems for some fixed $\Sigma$ such that $A\cup B\neq\Sigma^*$ and $A\cup B\in\text{PSPACE}$. Does it follow that $A\cup B$ is $\text{PSPACE}$-complete?

The condition "$A\cup B\in\text{PSPACE}$" is redundant since it is always true given that $A,B$ are $\text{PSPACE}$ problems.

It does not follow that $A\cup B$ is $\text{PSPACE}$-complete.
For example, let $A$ be a $\text{PSPACE}$-complete language. Let string $s\notin A$. Let $B=\overline A \setminus\{s\}$, which is a $\text{PSPACE}$-complete language. $A\cup B=\Sigma^*\setminus\{s\}\not=\Sigma^*$ is a language for which the membership problem can be determined in constant space (and constant time). $A\cup B$ is not $\text{PSPACE}$-complete.


I don't think people have established any sufficient condition for the union of $\text{PSPACE}$-hard (or complete) problems to be $\text{PSPACE}$-hard (complete) except the obvious ones.

Here is an obvious one. If $A$ is a $\text{PSPACE}$-complete language in which all strings start with $0$ while $B$ is a $\text{PSPACE}$-complete language in which all strings start with $1$, the $A\cup B$ is a $\text{PSPACE}$-complete language.

$\endgroup$
2
  • $\begingroup$ Do I understand it correctly that PSPACE complete problems are not closed under intersections either? Even if we assume that $A\cap B\neq\varnothing$? $\endgroup$ May 3, 2023 at 10:10
  • 2
    $\begingroup$ Correct. For example, let $A$ be PSPACE complete and $s\in A$. Then $A\cap (\overline A\cup\{s\})=\{s\}$. For another example, let $X$ be a PSPACE-complete language and $Y$ a nonempty finite language. Then both $0X\cup Y$ and $1X\cup Y$ are PSPACE-complete. Their intersection is $Y$. $\endgroup$
    – John L.
    May 3, 2023 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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