<p>It is indeed still open, and for good reason.</p>
<p>A combinatorial conjecture of Rudich and Impagliazzo implies that <span class="math-container">$\mathsf{P} \neq \mathsf{NP}\cap\mathsf{coNP}$</span> relative to a random oracle implies <span class="math-container">$\mathsf{P} \neq \mathsf{NP}$</span>.</p>
<p>Further, this combinatorial conjecture is <em>true</em>. This was <a href="https://ieeexplore.ieee.org/document/856739" rel="nofollow noreferrer">proven</a> in a lovely paper by Kahn, Saks, and Smyth in 1999.</p>
<p>Edit: My mistake, this paper is for <span class="math-container">$\mathsf{NP}\cap\mathsf{coNP}\subseteq\mathsf{AvgP}$</span> under a random oracle, not <span class="math-container">$\mathsf{P}$</span>!</p>

CC BY-SA 4.0
2024-12-12T07:07:59.343Z
Is this right? I can't access the full paper, but the abstract says that P = NP implies only that $\mathsf{NP\cap coNP\subseteq i{.}o{.}AvgP}$ relative to a random oracle, rather than $\mathsf{NP\cap coNP=P}$ relative to a random oracle.
Emil Jeřábek
CC BY-SA 4.0
2024-12-12T10:46:28.087Z
Having glimpsed at the paper and others referenced, it indeed doesn't seem to claim anything about P = NP $\cap$ coNP itself relative to oracles, although they do suggest that it may be strengthened to NP $\cap$ coNP being contained in AvgP relative to random oracle, the class of problems with a polytime algorithm which is correct on positive fraction of instances. While interesting, still a far cry from P itself.
Wojowu
CC BY-SA 4.0
2024-12-12T14:42:46.827Z
@EmilJeřábek Ah thank you, you are right! It is for $\mathsf{AvgP}$, not $\mathsf{P}$.
Stefan G.
CC BY-SA 4.0
2024-12-12T04:51:35.273Z
2024-12-12T14:44:54.520Z
2024-12-12T14:44:54.520Z
Stefan G.
<p>In 1981 Bennett and Gill have established the first set of separation results relative to a random oracle. In particular, for almost all oracles <span class="math-container">$A$</span>, we have <span class="math-container">$\mathsf{P}^A\neq\mathsf{NP}^A\neq\mathsf{coNP}^A$</span>. Furthermore, given oracle access to a random <em>permutation</em> <span class="math-container">$\pi$</span>, we have <span class="math-container">$\mathsf{P}^\pi\neq\mathsf{NP}^\pi\cap\mathsf{coNP}^\pi$</span>. However, the question of whether <span class="math-container">$\mathsf{P}^A$</span> equals <span class="math-container">$\mathsf{NP}^A\cap\mathsf{coNP}^A$</span> relative to random oracle is left unanswered.</p>
<p>I have found a handful of papers which mention this problem, but the most recent one I found being Vereshchagin's <a href="https://ieeexplore.ieee.org/abstract/document/377048" rel="noreferrer">NP-sets are Co-NP-immune relative to a random oracle</a>, from 1995. I was curious if there has been any more recent work on this problem.</p>
<blockquote>
<p>Are there any more recent works which shed any light on this question?</p>
</blockquote>

<cc.complexity-theory><complexity-classes><oracles><random-oracles>
Is $\sf P\neq NP\cap coNP$ relative to random oracle still open?
Wojowu
# Is $\sf P\neq NP\cap coNP$ relative to random oracle still open?

(Asked by: username_0 on 2024-12-10)

In 1981 Bennett and Gill have established the first set of separation results relative to a random oracle. In particular, for almost all oracles $A$, we have $\mathsf{P}^A\neq\mathsf{NP}^A\neq\mathsf{coNP}^A$. Furthermore, given oracle access to a random *permutation* $\pi$, we have $\mathsf{P}^\pi\neq\mathsf{NP}^\pi\cap\mathsf{coNP}^\pi$. However, the question of whether $\mathsf{P}^A$ equals $\mathsf{NP}^A\cap\mathsf{coNP}^A$ relative to random oracle is left unanswered.

I have found a handful of papers which mention this problem, but the most recent one I found being Vereshchagin's [NP-sets are Co-NP-immune relative to a random oracle](https://ieeexplore.ieee.org/abstract/document/377048), from 1995. I was curious if there has been any more recent work on this problem.

> Are there any more recent works which shed any light on this question?

**Tags:** cc.complexity-theory, complexity-classes, oracles, random-oracles


---

## 1 answers

### Answer by username_1 on 2024-12-12. Score: 2

It is indeed still open, and for good reason.

A combinatorial conjecture of Rudich and Impagliazzo implies that $\mathsf{P} \neq \mathsf{NP}\cap\mathsf{coNP}$ relative to a random oracle implies $\mathsf{P} \neq \mathsf{NP}$.

Further, this combinatorial conjecture is *true*. This was [proven](https://ieeexplore.ieee.org/document/856739) in a lovely paper by Kahn, Saks, and Smyth in 1999.

Edit: My mistake, this paper is for $\mathsf{NP}\cap\mathsf{coNP}\subseteq\mathsf{AvgP}$ under a random oracle, not $\mathsf{P}$!

> **Comments:**
> **username_2**: Is this right? I can't access the full paper, but the abstract says that P = NP implies only that $\mathsf{NP\cap coNP\subseteq i{.}o{.}AvgP}$ relative to a random oracle, rather than $\mathsf{NP\cap coNP=P}$ relative to a random oracle.  
> **username_0**: Having glimpsed at the paper and others referenced, it indeed doesn't seem to claim anything about P = NP $\cap$ coNP itself relative to oracles, although they do suggest that it may be strengthened to NP $\cap$ coNP being contained in AvgP relative to random oracle, the class of problems with a polytime algorithm which is correct on positive fraction of instances. While interesting, still a far cry from P itself.  
> **username_1**: @EmilJeřábek Ah thank you, you are right! It is for $\mathsf{AvgP}$, not $\mathsf{P}$.  

---

