<p>I am trying to find some references or arguments for results of the form, where <span class="math-container">$X,Y$</span> vary over complexity classes, typically with <span class="math-container">$X\subseteq Y$</span>, and <span class="math-container">$A,B$</span> are disjoint languages that are <span class="math-container">$Y$</span>-hard:</p>
<blockquote>
<p>Unless !!! there is no <span class="math-container">$X$</span>-separator of <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, i.e. there is no <span class="math-container">$S\in X$</span> with <span class="math-container">$A \subseteq S$</span> but <span class="math-container">$S\cap B = \emptyset$</span>.</p>
</blockquote>
<p>Some clarifications/further points:</p>
<ul>
<li>I am particularly interested in when <span class="math-container">$Y = \mathbf{PSPACE}$</span> and <span class="math-container">$X = \mathbf{NP}$</span>. I can find related questions when <span class="math-container">$Y=\mathbf{NP}$</span> and <span class="math-container">$X = \mathbf P$</span> around the proof complexity literature, and when, say, <span class="math-container">$Y=\Sigma^0_1$</span> and <span class="math-container">$X=\Delta^0_1$</span> in the recursion theory literature.</li>
<li>'!!!' can be any statement that is widely considered to be false or surprising, e.g. 'false' but also '<span class="math-container">$\mathbf P = \mathbf{NP}$</span>' or '<span class="math-container">$\mathbf{NP}=\mathbf{PSPACE}$</span>', and even stronger ones like '<span class="math-container">$\mathbf P/\mathrm{poly} \supseteq\mathbf{NP}$</span>' or 'integer-factoring <span class="math-container">$\in \mathbf P/\mathrm{poly}$</span>'. I am also happy for a literature reference replacing 'unless !!!' with 'we conjecture that / it is conjectured that'.</li>
<li>I would also be particularly interested to know of stronger results that establish the above statement <strong>for all such <span class="math-container">$A,B$</span></strong>, for appropriate <span class="math-container">$X,Y$</span>. Note that such a strenghening does not hold when <span class="math-container">$Y=\mathbf{NP}$</span> and <span class="math-container">$X = \mathbf P$</span> due to the Clique-Colouring pair [Pud03], but does hold when <span class="math-container">$Y=\mathbf{\Sigma^1_1}$</span> and <span class="math-container">$X=\mathbf{Borel}$</span> [Luz30]. Does such a strengthening hold when <span class="math-container">$Y=\mathbf{PSPACE}$</span> and <span class="math-container">$X=\mathbf{NP}$</span> (unless !!!)?</li>
</ul>
<p>[Pud03] Pudlák, Pavel. &quot;On reducibility and symmetry of disjoint NP pairs.&quot; Theoretical Computer Science 295.1-3 (2003): 323-339.</p>
<p>[Luz05] Luzin, Nikolaĭ Nikolaevich, and Henri Léon Lebesgue. &quot;Leçons sur les ensembles analytiques: et leurs applications.&quot; (1905).</p>

CC BY-SA 4.0
2024-03-27T21:33:32.080Z
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?
Emil Jeřábek
CC BY-SA 4.0
2024-03-27T21:37:55.327Z
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.
Emil Jeřábek
CC BY-SA 4.0
2024-03-27T22:14:05.350Z
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.
Emil Jeřábek
CC BY-SA 4.0
2024-03-28T10:44:38.210Z
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.
Anupam Das
CC BY-SA 4.0
2024-03-28T14:49:29.320Z
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.
Neal Young
CC BY-SA 4.0
2024-03-28T17:14:10.063Z
There is the verb 'is'. To be clear '!!!' is a metavariable for a mathematical statement (as explained in second bullet point).
Anupam Das
CC BY-SA 4.0
2024-03-29T06:45:21.880Z
I of course meant "separated by a disjoint $Y$-pair that is a language (i.e., total)". This does require $Y$ to be closed under complement, and shows that under this condition, questions about hardness of separation for disjoint $Y$-pairs degenerate to questions about includion of $Y$ in another class.
Emil Jeřábek
<np><complexity><pspace><promise-problems><separation>
Separating disjoint PSPACE-hard sets by NP-separators (and some variants)
Anupam Das
# Separating disjoint PSPACE-hard sets by NP-separators (and some variants)

(Asked by: username_0 on 2024-03-27)

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

**Tags:** np, complexity, pspace, promise-problems, separation
> **Comments:**
> **username_1**: 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?  
> **username_1**: 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.  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: There is the verb 'is'. To be clear '!!!' is a metavariable for a mathematical statement (as explained in second bullet point).  
> **username_1**: I of course meant "separated by a disjoint $Y$-pair that is a language (i.e., total)". This does require $Y$ to be closed under complement, and shows that under this condition, questions about hardness of separation for disjoint $Y$-pairs degenerate to questions about includion of $Y$ in another class.  

---

## 0 answers

