Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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."

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.