Pergunta

I've been trying to understand why, for instance, even though there are oracles $A$ for which $P^A \neq NP^A$, we still don't know if $P=NP$.

As I understand it, it's because it's easy to construct languages that can only be efficiently taken advantage of in a non-deterministic settings. For example, pick a single arbitrary string and call that your language; then all you need is non-determinism to try every string and you're okay in $NP$, yet still trapped into brute force in $P$.

My question is, what exactly separates this from a regular $NP$ problem? Why is this fundamentally different from an $NP$ problem that accepts only on some arbitrary predetermined certificate (or is it even possible to construct such a problem)?

Is it just the fact that $NP$ problems are required to have some sort of structure, whereas in the relativised case we're free to build our language arbitrarily? Or is there some deeper difference I'm missing?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top