1
$\begingroup$

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}$?

$\endgroup$
2
  • $\begingroup$ Take a look at this question: cstheory.stackexchange.com/questions/799/…. $\endgroup$ Sep 25, 2018 at 19:31
  • $\begingroup$ 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. $\endgroup$ Sep 26, 2018 at 5:09

1 Answer 1

1
$\begingroup$

Yes.

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.

$\endgroup$

Your Answer

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