# Assuming NP≠coNP, do we have a similar theorem to Ladner's?

We have that $$\mathrm{NP\neq coNP\iff NP\neq NP\cap coNP}$$.

So by assuming that $$\mathrm{NP\neq coNP}$$, can we prove the existence of intermediate problem between $$\mathrm{NP}$$-complete and $$\mathrm{NP\cap coNP}$$?

• Take a look at this question: cstheory.stackexchange.com/questions/799/…. Sep 25, 2018 at 19:31
• I personally do not believe that Uwe Schoening can give a general framework applicable to this case. It takes just one missing piece to break all the framework in various cases. Sep 26, 2018 at 5:09

Before answering your question, let me make it clear that the reasoning provided in the link Filmus suggests above will not work for $$\mathrm{NP\cap coNP}$$, since this nasty class refuses to be efficiently enumerated. Also, it is very unclear to talk about $$\mathrm{FP^{NP\cap coNP}}$$-reductions, not to mention how to enumerate them. Very faint an idea to do complexity theory that way.
By Ladner's splitting theorem for $$p$$-degrees, every non-zero $$p$$-degrees splits into two lesser incomparable $$p$$-degrees.
Now, by the assumption that $$NP\neq NP\cap coNP$$, the $$NP$$-complete degree is separated from $$P$$ (zero $$p$$-degree). Applying the splitting theorem and downward closure for $$p$$-m-reduction of $$NP$$, we have that the complete degree $$\mathcal{C}$$ splits to two lesser degrees $$\mathcal{A}$$ and $$\mathcal{B}$$.
Whenever $$\mathcal{C}$$ splits into $$\mathcal{A}$$ and $$\mathcal{B}$$, we have that $$\mathcal{C\subseteq P^{A, B}}$$. And, we know that $$\mathrm{P^{NP\cap coNP}=NP\cap coNP}$$.
So, at least $$\mathcal{A}$$ or $$\mathcal{B}$$ must be outside of $$NP\cap coNP$$. That is the intermediate degree you are seeking.