Why is Relativization a barrier?

Question

When I was explaining the Baker-Gill-Solovay proof that there exists an oracle with which we can have, $\mathsf{P} = \mathsf{NP}$, and an oracle with which we can have $\mathsf{P} \neq \mathsf{NP}$ to a friend, a question came up as to why such techniques are ill-suited for proving the $\mathsf{P} \neq \mathsf{NP}$ problem, and I couldn't give a satisfactory answer.

To put it more concretely, if I have an approach to prove $\mathsf{P} \neq \mathsf{NP}$ and if I could construct oracles to make a situation like above happen, why does it make my method invalid?

Any exposition/thoughts on this topic?

Answer 1

To put it more concretely, if I have an approach to prove P≠NP and if I could construct oracles to make a situation like above happen, why does it make my method invalid?

Note that the latter “if” is not a condition, because Baker, Gill, and Solovay already constructed such an oracle. It is just a mathematical truth that (1) there exists an oracle relative to which P=NP, and that (2) there exists an oracle relative to which P≠NP.

This means that if you have an approach to prove P≠NP and the same proof would equally prove a stronger result “P^A≠NP^A for all oracles A,” then your approach is doomed to fail because it would contradict (1).

In other words, there is some fundamental difference between proving P≠NP and proving e.g. the time hierarchy theorem, because the proof of the latter just uses diagonalization and is equally applicable to any relativized world.

Of course, this does not mean that there is no proof for P≠NP. Such a proof (if one exists) must fail to prove the stronger result mentioned above. In other words, some part of the proof must distinguish the nonrelativizing world from arbitrary relativized worlds.

Answer 2

There are already good answers, but I would like to add a few small points.

Assume that we have a technique to solve problems, e.g. diagonalization. Assume that we want to show that the technique cannot solve a specific problem e.g. $\mathsf{P}$ vs. $\mathsf{NP}$. How can be show this?

Before going further, note that a technique like diagonalization is not a formal concept here (though we can make it so). Moreover the fact that the technique cannot solve the problem by itself doesn't mean that it is not useful in solving the problem at all, we might be able to modify it and/or combine it with other techniques to solve the problem.

Now, let's get back to the question. One way to show that a technique cannot solve a specific problem is to show that if it could it would also work in a different framework for solving another question, and the answer that we would get in that case would be wrong. This is what happens here. If the diagonalization could separate $\mathsf{NP}$ from $\mathsf{P}$ then the same argument could be used to separate $\mathsf{NP^A}$ from $\mathsf{P^A}$ for all $A$. But we know that there is an oracle such that this is false (take any $\mathsf{PSpace}$-complete problem as the oracle). So diagonalization cannot separate $\mathsf{NP}$ from $\mathsf{P}$.

The essential point in this argument is a kind of transfer principle:

we can transfer a diagonalization argument for TMs without oracle to TMs with oracles.

This is possible here because diagonalization arguments are based on simulation of machines, moreover the simulation doesn't depend on the internals of machines but only on the final answers from these simulations. This kind of diagonalization is referred to as simple diagonalization. In a simulation it doesn't matter how the machine works, we care only the final answer of the machine. Adding an oracle will not change this so the simulation and the argument will work also in the framework where we have oracles.

More formally, we can think of a diagonalization argument as a function from a class of machines (say $\mathsf{P}$) to instances showing that the machine cannot solve a problem (say $SAT$). This counterexample function is the diagonalization function. A diagonalization is simple if the counterexamples it gives do not depend on the internals of the machines, i.e. if two polynomial time DTMs have the same language then the counterexample showing that they cannot solve $SAT$ given by the diagonalization function is the same.

You may wonder if this is a big restriction? Why would the counterexample need to depend on the internal structure of the machine? Can we prove separations using diagonalization that cannot be proved using simple diagonalization? The answer is yes. In fact Kozen shows in his 1978 paper "Indexing of subrecursive classes" (3 years after BGS result) that if $\mathsf{NP}$ can be separated from $\mathsf{P}$ then there is a general diagonalization argument for it. And in practice such arguments have been found. For example, Fortnow and van Melkebeek's time-space lower-bounds for SAT (2000) use a technique called indirect diagonalization that gives a non-simple diagonalization.

So is the claim that diagonalization cannot solve $\mathsf{P}$ vs. $\mathsf{NP}$ incorrect? Well, in general what experts mean by diagonalization here is simple diagonalization and there is a good reason for that.

The general diagonalization arguments are so general that it doesn't really make much sense to call them a technique, you can easily turn any separation argument into a diagonalization argument without much insight: If we already have some way of separating two complexity classes, we can pick a function in the larger class not in the smaller one. Take any enumeration of the machines in the smaller class. Let $M$ be any machines in the enumeration. We have to define the counterexample for $M$. But we already know that $M$ cannot solve the problem, so there exists instance showing this, define the value of the diagonalization function on $M$ to be that instance. This is the big-picture view, if you want to see the details check Kozen's paper.

Summery:

• When experts say "diagonalization cannot solve $\mathsf{P}$ vs. $\mathsf{NP}$" what they mean is "simple diagonalization cannot solve $\mathsf{P}$ vs. $\mathsf{NP}$" not the general one.
• The reason simple diagonalization cannot separate $\mathsf{NP}$ from $\mathsf{P}$ is that it transfers to the framework with oracles (in the literature it is stated as "diagonalization relativized") and the separation does not hold there.
• The reason this transfer from oracle-less framework to framework with oracles works is that simple diagonalization is based on black-box simulation of TMs and it doesn't matter how machines works, whether it has an oracle or not.

Two good papers to learn more about diagonalization are

• Lance Fortnow's survey paper "Diagonalization", 2001, and
• Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova's paper "An Axiomatic Approach to Algebrization", 2009. (Note that algebraization is an extension of simple diagonalization.)

Answer 3

Let $\mathrm{A}$ and $\mathrm{B}$ be two complexity classes. A separation ($\mathrm{A} \neq \mathrm{B}$) or collapse ($\mathrm{A} = \mathrm{B}$) is said to relativize if for all oracles $\mathrm{O}$ we have $\mathrm{A}^\mathrm{O} \neq \mathrm{B}^\mathrm{O}$ or $\mathrm{A}^\mathrm{O} = \mathrm{B}^\mathrm{O}$ respectively. The Baker-Gill-Solovay proof tells us that $P = NP$ or $P \neq NP$ does not relativize.

Why is this a problem? When this proof came out, the majority of techniques and tricks we knew to separate or collapse complexity classes 'relativized', in that they work with respect to any oracle. For instance, the time hierarchy theorem (as well as the space and nondeterministic versions of it) 'relativize': they prove separations for classes for which this separation relativizes, and in fact, they prove the stronger result that the separation holds with respect to any oracle.

If a technique or trick works regardless of whether there is an oracle present, then it cannot possibly prove $P = NP$ or $P \neq NP$ by the above argument. This means that a large number of tricks and techniques that we know of don't work on this problem (or indeed on a lot of open problems). You can also use it as a sanity check for any purported $P \neq NP$ proof: check whether the idea fails to hold in the presence of a $\mathrm{PSPACE}$-complete oracle - if it still works, then it is wrong.