The P vs NP question : Relativization and its importance

1.0: Relativization

In this section we discuss the importance of relativization as a technique and how it has provided for new directions in complexity theory. We will also see why this otherwise powerful technique is insufficient to resolve the P-NP dilemma but provides counter-arguments against other techniques and hence has continued to be useful in complexity theory.

1.1: Introduction

Relativization was first introduced by Baker, Gill and Solovay[2.1] and has continued to be an important technique because it provides arguments against proofs that try to solve the P versus NP question. The general idea is as explained below:

Suppose we can show for some statement S that there exists an oracle A such that S fails relative to A in some oracle model. Now any proof that S holds must not relativize in that model or otherwise that statement would also hold relative to A. If we can also find an oracle relative to which S holds then no relativizable technique can decide the truth of S. Furthermore, once a problem has been shown to have two conflicting relativized versions, it is believed that it is beyond the current state of mathematics to solve such a problem.[2.2]

This belief is why the method of relativization works as a counter-argument (and in favor of non-relativizing techniques) for techniques that decide important statements like whether or not P equals NP. Therefore, if someone came up with a proof that P = NP and that proof could also be used to show that PA = NPA then it is doomed to fail because it would contradict the statement PB does not equal NPB which has been shown by Baker, et. al.[2.1] 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 non relativizing world from arbitrary relativized worlds.

1.2: Why diagonalization won’t work as a proof

An important consequence of relativization is that it seems highly unlikely that a diagonalization proof can be shown to work because of the nature of diagonalization proofs. Any diagonalization proof at its heart is a simulation of one turing machine by another. If we in turn provide oracles to both these machines it would show via the same proof that this result is true for any oracle in general. Again, using the fact that this is not the case for P and

NP we can easily see that simple simulation techniques are bound to fail.

Another handy implication of the relativization technique is the relativized separation of classes. Relativized separations rely on the access mechanisms to oracles. The proof by Baker, et. al.[2.1] does exactly this and hence it is unclear as to whether showing that two classes relativize implies anything about their computational power. As a consequence, following the seminal work by Baker[2.1] a lot of counter-arguments in complexity theory have used the relativization technique.

1.3: How relativization works as a negative-proof technique

The first important oracle hypothesis which was refuted 11 years after its creation was the “random oracle hypothesis” which claimed that - Given access to a random oracle, the base classes can be treated as if they were non-relativizing. The standard way of constructing a random oracle as proposed by the paper by Bennett and Gill[2.3] was to consider an oracle which could contain any string with the uniform probability of ½. Hence, if there were relativized results that were true with respect to this random oracle, they would also hold for the base classes in its absence. The hypothesis was useful from the standpoint guiding a technique for the next generation of proof mechanisms rather than finding an astounding result. Unfortunately, it was misleading in the sense that this hypothesis claimed a lot more than what was possible and did not take into consideration specific oracle counterexamples.

An interesting result was obtained by Book Long and Selman in a paper titled “Quantitative Relativizations of Complexity Classes”[2.4] where they showed that for comparable access mechanisms a relativized separation also worked in the non-relativizing case. This is perhaps the only real problem with using the relativization technique. A direct implication of this result in the P vs NP case is that if nondeterministic machines are restricted to only polynomially many queries then it is quite possible for the relativized separation of P and NP to imply P does not equal NP. In general, this meant that a proof within the relativized world with the restriction on access mechanisms could still be meaningful. This was in some sense a direct consequence of the “random oracle hypothesis” and was optimistically named the theory of “positive relativization”.

Fortnow and Sipser[2.5] came up with an oracle A such that co-NPA  ̸⊆ IPA and after a few years, it was shown by Lund, Fortnow, Karloff and Nisan[2.6] that the polynomial hierarchy is contained within the space of interactive proofs IP. A direct implication of this result was IP = PSAPCE, as discussed in Shamir’s paper[2.7] which itself is an example of a proof that employed a non-relativizing technique. This proof uses arithmetization and hence does not relativize. Subsequently, it was shown with probability 1 that for a random oracle A, IPA is not the same as PSPACEA. Given that IP = PSPACE, this proof convincingly refuted the random oracle hypothesis. The next section discusses a great advancement in complexity theory which provides us with two unequal classes that can be collapsed by an oracle.