<p>It seems that there is a confusion in the question between oracles resulting in equality vs. oracles resulting in separation. It is easy to find natural oracles resulting in equality. Oracles for separation is a different matter and your question does not contain an example for them. </p>

<p>We don't have that many techniques for separating complexity classes and relativized separations are no different. The examples you get are expected to result from those techniques so it is unlikely that such oracles are known.</p>

<p>As far as I know, diagonalization is the only method we know of that can separate non-small complexity classes, so no surprise the oracles separating $\mathsf{NP}$ from $\mathsf{P}$ are such sets.</p>

CC BY-SA 3.0
2012-12-21T17:43:25.033Z
2012-12-21T17:49:43.407Z
2012-12-21T17:49:43.407Z
Kaveh
<p>The oracles that are used in relativized collapses or separations of complexity classes rarely represent $natural$ algorithmic problems. They are typically constructed "artificially" with techniques like diagonalization, for the sole purpose of achieving the relativized collapse or separation. A notable exception is that for any ${\bf PSPACE}$-complete set $L$ it holds that ${\bf P}^L={\bf NP}^L$. This indeed leads to "natural relativized worlds," since there are  ${\bf PSPACE}$-complete languages that correspond to  natural algorithmic tasks. Generally, I am looking for such examples, where the oracle represents a natural problem. (And, of course, it is not trivially implied by the above example). </p>

<p>In particular, is there any such known "natural relativized world" in which ${\bf P}$ and ${\bf NP}$ are separated?</p>

<p>$Note:$ A random oracle here does not count as natural, because it does not represent a natural algorithmic problem. It rather represents that a statement holds for almost all oracles, regardless to their "naturality."</p>

<cc.complexity-theory><complexity-classes><oracles>
Natural relativized worlds
Andras Farago
# Natural relativized worlds

(Asked by: username_0 on 2012-12-21)

The oracles that are used in relativized collapses or separations of complexity classes rarely represent $natural$ algorithmic problems. They are typically constructed "artificially" with techniques like diagonalization, for the sole purpose of achieving the relativized collapse or separation. A notable exception is that for any ${\bf PSPACE}$-complete set $L$ it holds that ${\bf P}^L={\bf NP}^L$. This indeed leads to "natural relativized worlds," since there are ${\bf PSPACE}$-complete languages that correspond to natural algorithmic tasks. Generally, I am looking for such examples, where the oracle represents a natural problem. (And, of course, it is not trivially implied by the above example).

In particular, is there any such known "natural relativized world" in which ${\bf P}$ and ${\bf NP}$ are separated?

$Note:$ A random oracle here does not count as natural, because it does not represent a natural algorithmic problem. It rather represents that a statement holds for almost all oracles, regardless to their "naturality."

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


---

## 1 answers

### Answer by username_1 on 2012-12-21. Score: 2

It seems that there is a confusion in the question between oracles resulting in equality vs. oracles resulting in separation. It is easy to find natural oracles resulting in equality. Oracles for separation is a different matter and your question does not contain an example for them.

We don't have that many techniques for separating complexity classes and relativized separations are no different. The examples you get are expected to result from those techniques so it is unlikely that such oracles are known.

As far as I know, diagonalization is the only method we know of that can separate non-small complexity classes, so no surprise the oracles separating $\mathsf{NP}$ from $\mathsf{P}$ are such sets.


---

