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

  • $\begingroup$ 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? $\endgroup$ Mar 27 at 21:33
  • $\begingroup$ 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. $\endgroup$ Mar 27 at 21:37
  • $\begingroup$ 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. $\endgroup$ Mar 27 at 22:14
  • $\begingroup$ 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. $\endgroup$
    – Anupam Das
    Mar 28 at 10:44
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Mar 28 at 14:49


Your Answer

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