2
$\begingroup$

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

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

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

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