New answers tagged oracles
1
vote
Is $\sf P\neq NP\cap coNP$ relative to random oracle still open?
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 $\...
- 281
Top 50 recent answers are included