# Unions of PSPACE-comlete problems that are PSPACE-complete?

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)?

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.

• 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$? May 3, 2023 at 10:10
• 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$. May 3, 2023 at 13:22