# Separating disjoint PSPACE-hard sets by NP-separators (and some variants)

I am trying to find some references or arguments for results of the form, where $$X,Y$$ vary over complexity classes, typically with $$X\subseteq Y$$, and $$A,B$$ are disjoint languages that are $$Y$$-hard:

Unless !!! there is no $$X$$-separator of $$A$$ and $$B$$, i.e. there is no $$S\in X$$ with $$A \subseteq S$$ but $$S\cap B = \emptyset$$.

Some clarifications/further points:

• I am particularly interested in when $$Y = \mathbf{PSPACE}$$ and $$X = \mathbf{NP}$$. I can find related questions when $$Y=\mathbf{NP}$$ and $$X = \mathbf P$$ around the proof complexity literature, and when, say, $$Y=\Sigma^0_1$$ and $$X=\Delta^0_1$$ in the recursion theory literature.
• '!!!' can be any statement that is widely considered to be false or surprising, e.g. 'false' but also '$$\mathbf P = \mathbf{NP}$$' or '$$\mathbf{NP}=\mathbf{PSPACE}$$', and even stronger ones like '$$\mathbf P/\mathrm{poly} \supseteq\mathbf{NP}$$' or 'integer-factoring $$\in \mathbf P/\mathrm{poly}$$'. I am also happy for a literature reference replacing 'unless !!!' with 'we conjecture that / it is conjectured that'.
• I would also be particularly interested to know of stronger results that establish the above statement for all such $$A,B$$, for appropriate $$X,Y$$. Note that such a strenghening does not hold when $$Y=\mathbf{NP}$$ and $$X = \mathbf P$$ due to the Clique-Colouring pair [Pud03], but does hold when $$Y=\mathbf{\Sigma^1_1}$$ and $$X=\mathbf{Borel}$$ [Luz30]. Does such a strengthening hold when $$Y=\mathbf{PSPACE}$$ and $$X=\mathbf{NP}$$ (unless !!!)?

[Pud03] Pudlák, Pavel. "On reducibility and symmetry of disjoint NP pairs." Theoretical Computer Science 295.1-3 (2003): 323-339.

[Luz05] Luzin, Nikolaĭ Nikolaevich, and Henri Léon Lebesgue. "Leçons sur les ensembles analytiques: et leurs applications." (1905).

• It's rather unclear to me what the question really is. There are disjoint PSPACE-complete sets that can be separated by a set with trivial complexity (e.g., let $A=\{0w:w\in \mathrm{QBF}\}$, $B=\{1w:w\in \mathrm{QBF}\}$), and there are disjoint PSPACE-complete sets whose every separator is PSPACE-hard (e.g., let $A$ be QBF, and $B$ be its complement). Does any of this answer the question? Mar 27 at 21:33
• Generally speaking, there is hardly any point in considering disjoint $Y$-pairs as a separate complexity class if $Y$ is closed under complement, as then any such pair can be simply separated by a $Y$-language. Mar 27 at 21:37
• Another way to state the same thing: unlike disjoint NP-pairs, there exists a complete disjoint PSPACE pair, namely $(\mathrm{QBF,\overline{QBF}})$, and it is as hard as PSPACE itself. Mar 27 at 22:14
• Right, sorry, my 3rd bullet point does not make sense as you say, as there are always pairs with trivial separators. But I do not understand your second comment: this is true for any $Y$-complete pairs, not just ones closed under complement. So sure, while there may indeed be complete and trivial disjoint $Y$-pairs, couldn't there be specific pairs that have attracted particular interest? E.g. in recursion theory the set of TMs that reach a 'looping state' and the set of halting machines are both $\Sigma^0_1$-complete sets that are known to have no $\Delta^0_1$-separator. Mar 28 at 10:44
• I'm confused. The block-quoted sentence starting with "Unless..." is not a sentence? There is no verb. So I'm not sure what kind of arguments you are looking for. Mar 28 at 14:49