by

Relativization Barrier

I am back in Atlanta after attending an awesome Barriers Workshop. This workshop is mainly about the barriers in resolving P vs NP problem and possible techniques to overcome these barriers. It is a five day workshop covering circuits lower bounds, arithmetic circuits, proof complexity, learning theory and pseudo-random generators. I enjoyed every talk and panel discussions. Everybody seemed very positive that P \neq NP.

Today’s post is a quick introduction to Relativization Barrier. I will write separate posts about natural proofs and algebrization barriers soon. Relativization Barrier is one of the first barriers we learn in an introductory graduate level complexity course.

In relativized world we grant the Turing machine M the access to an oracle that could compute some function A in a single time step. Such a machine, called oracle TM, computes relative to A, is represented by M^A. Oracle TMs are used in Turing-reducibility, a generalization of mapping-reducibility.

The method of diagonalization relativizes i.e.,  any separation result in the real world, proved using diagonalization, extends to the relativized world. Baker, Gill and Solovay [BGS’75] showed that there exists oracles A and B for which P^A and NP^A are provably different and P^B and NP^B are provably equal. That is P vs NP has different answers in different worlds !! Hence techniques such as diagonalization, cannot be used to resolve P versus NP.

Theorem : An oracle A exists such that P^A \neq NP^A. An oracle B exists such that P^B = NP^B.

Let B be any PSPACE-complete problem. We have NP^B \subseteq NPSPACE \subseteq PSPACE \subseteq P^B. The first and third containments are trivial and the second containment follows from Savitch’s theorem. Hence P^B = NP^B. Constructing A is a non-trivial task. Look at Sipser’s book (page 350) for details of constructing A.

Therefore any solution to the P versus NP problem will require non-relativizing techniques i.e., techniques that exploit properties of computation that are specific to the real world i.e., techniques that analyze the computations not just simulate them.

References :

  • [BGS’75] T. Baker, J. Gill, and R. Solovay : Relativizations of the P=?NP question. SIAM J. Comput., 4:431–442, 1975.

Baker, Gill and Solovay [BGS’75] showed that techniques such as diagonalization,
cannot be used to resolve P versus NP. Such techniques would work in [relativized]
world, where both P and NP machines could compute some function
f in a single time step.
However, there are some relativized
worlds where P = NP, and other relativized worlds
where P != NP. Therefore any solution to the P versus NP
problem will require non-relativizing techniques i.e., techniques
that exploit properties of computation that are specific to
the real world.

5 thoughts on “Relativization Barrier”

  1. Pingback: Logspace vs Polynomial time « My Brain is Open

  2. Pingback: Getting On Base With P=NP « Gödel’s Lost Letter and P=NP

  3. Pingback: Proofs, Barriers and P vs NP | Q&A System

  4. Pingback: Proofs, Barriers and P vs NP | CL-UAT

  5. Pingback: Web of C-lief: conjectures vs. model assumptions vs. scientific beliefs | Theory, Evolution, and Games Group

Leave a comment