3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ There are also oracles with respect to which P equals NP. $\endgroup$ – Yuval Filmus May 8 at 16:08
3
$\begingroup$

The reason has little to do with the problems in $\mathbf{P}$ and $\mathbf{NP}$ themselves; it is due to the computation models they describe. Recall that, if $A$ and $B$ are complexity classes, $A^B$ only really makes sense if $A$ can be expressed as a class of machines which can be equipped with oracle access (to the problems in $B$). $A^B$ does not make sense if $A$ cannot be expressed in terms of machines (which can use oracles).

This means the class $A^B$ is not obtained simply by taking the class $A$ (as a set of languages) and performing some operation on them using $B$ as a parameter (as the rather deceivingly simple "exponentiation-looking" notation would lead you to believe). Rather, it is a class belonging to a machine model of its own accord, namely the machine model of $A$ given oracle access to problems in $B$. In fact, it is rather surprising that the whole thing is well-defined, that is, that taking any two machine models for $A$ and granting both of them oracle access to $B$ yields the same class $A^B$ (actually, this only works if you are so careful as to give them both oracle access in a proper way).

That we can obtain relativizing results from certain (i.e., relativizing) proofs is, thus, even more surprising. As you can see, these are the sort of proofs which still work even if you replace the machine models with any closely-related ones (i.e., their oracle versions). Since they generalize in this way, they actually turn out to be very useful in that we can derive corollaries from them (for the respective relativized classes). An example of such a proof would be the inclusion $\mathbf{BPP} \subseteq \Sigma_2$.

In a nutshell, $\textbf{P}^A \neq \textbf{NP}^A$ does not really tell us anything about the relation of $\textbf{P}$ to $\textbf{NP}$ since $\textbf{P}^A$ (resp., $\textbf{NP}^A$) can be a class which is completely unrelated to $\textbf{P}$ (resp., $\textbf{NP}$). For an extreme example, consider what happens when $A$ is the class of languages which are (efficiently) reducible to the halting problem; in this case $\mathbf{P}^A$ contains languages which are not even recursively enumerable. And there are even classes which have been shown to be equal, but which do not relativize in almost any way (e.g., $\mathbf{IP}$ and $\mathbf{PSPACE}$).

$\endgroup$
  • $\begingroup$ Thank you for the excellent answer! I think I may see my confusion now. I was think of complexity classes strictly as sets of languages, without considering the fact that they refer to specific methods of computation. Thus, just because two complexity classes are the same, does not mean they will remain the same when you change their underlying models of computation, even if they're changed in the "same" way. Is that a correct assessment? $\endgroup$ – Steve Schwarcz May 8 at 16:54
  • 1
    $\begingroup$ @SteveSchwarcz Indeed, that happens because you are operating on the classes' models, not the classes themselves. (I commiserate with your confusion; I used to have it too :) $\endgroup$ – dkaeae May 8 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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