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 .

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 . 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 and are provably different and and 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 . An oracle B exists such that .

Let **B** be any PSPACE-complete problem. We have . The first and third containments are trivial and the second containment follows from Savitch’s theorem. Hence . 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.

### Like this:

Like Loading...

*Related*

Pingback: Logspace vs Polynomial time « My Brain is Open

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

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