<p>You are exactly right. The relativization operation $B\mapsto B^A$ is not well defined. 
P and P<sup>A</sup> are independently defined objects. The names are suggestive, but you cannot formally define P<sup>A</sup> from the set P. (You can define P from P<sup>A</sup> by setting A to be the empty set.)</p>

<p>Think of P<sup>A</sup> as being some kind of generalization of P, which equals P when A is empty, but otherwise may be different. Now if you only know the set P, it is not clear how to generalize this to get P<sup>A</sup>. As an analogy, if I asked you to generalize the real numbers, it's not clear what generalization I'm looking for. Am I thinking of fields, rings, vector spaces, etc.? The reason this happens is that while P is merely a set of languages, P<sup>A</sup> is defined in terms of a machine. This machine has the property that when A is empty it decides exactly the same languages as P. You could come up with some other machine, let's call it Q<sup>A</sup>, which also has the property that when A is empty decides the same languages as P. This does not mean that P<sup>A</sup> = Q<sup>A</sup> for all A. This would be analogous to asserting that if f(0)=g(0), then f and g are the same function.</p>

<p>Perhaps <a href="http://terrytao.wordpress.com/2009/08/01/pnp-relativisation-and-multiple-choice-exams/">this post by Terence Tao</a> will be helpful.</p>

CC BY-SA 3.0
2014-03-18T18:08:12.463Z
Thanks, Robin. That's another good answer, and the link to Tao's article is very helpful.
Suresh Venkat
CC BY-SA 3.0
2014-03-18T15:29:30.237Z
2014-03-18T15:29:30.237Z
Robin Kothari
<p>According to BGS theorem [1], there is an oracle $A$ such that $P^A\neq NP^A$. </p>

<p>If the relativization operation $B\mapsto B^A$ was a well-defined function, 
one would expect that from $B^A\neq C^A$ one would be able to conclude that $B\neq C$,
e.g. $P\neq NP$ would follow from BGS. However, $P\neq NP$ is still open.</p>

<p>Does that mean that relativization is not a well-defined function? </p>

<p>If so, do we have any example of two provably different relativizations of the same complexity class?</p>

<p>[1] T. P. Baker, J. Gill, and R. Solovay, "Relativizations of the P =? NP Question"</p>

CC BY-SA 3.0
2014-03-17T18:27:52.873Z
Baker-Gill-Solovay shows two oracles: one where P and NP are equal and one where they aren't. That answers your last question.
Suresh Venkat
CC BY-SA 3.0
2014-03-17T18:35:53.983Z
@SureshVenkat: if you mean that there are oracles $A,B$ such that $P^A\neq NP^A$ and $P^B=NP^B$ then this result (Ladner's theorem?) is actually the background of my question. I can see why $P^B=NP^B$ does not imply $P=NP$, but I don't see why $P^A\neq NP^A$ does not imply $P\neq NP$.
Michael
CC BY-SA 3.0
2014-03-17T20:55:08.537Z
@Kaveh would be helpful to point to specific answers. I did a quick scan of the *questions* and didn't see anything.
Suresh Venkat
CC BY-SA 3.0
2014-03-17T21:40:19.777Z
PS: the short answer to your question is that a relativization is not an extensional/functional operator on class of problems, even if the notation looks to imply otherwise. There is no general definition of relativization for problem classes,  relativizations are defined for _machine models_ and a single machine model can have several different relativized versions.
Kaveh
CC BY-SA 3.0
2014-03-17T23:13:59.710Z
pps: The example you are looking for is IP=PSpace provably but there are relativizations for IP and PSpace which are provably not equal, see [this question](http://cstheory.stackexchange.com/q/9934/186). If you want to read more about relativization you can start with Lance Fortnow's survey "[The role of relativization in complexity theory](http://www.cs.uchicago.edu/~fortnow/papers/relative.pdf)", 1994.
Kaveh
CC BY-SA 3.0
2014-03-18T15:34:59.837Z
fyi fortnow notes/admits in his abstract that complexity theorists both use and _"misuse"_ relativization.... it seems to be an admittedly gray area of complexity theory _at times_....
vzn
CC BY-SA 3.0
2014-03-18T21:18:28.523Z
@Suresh, I found these: [Techniques for proving that a sentence relativizes](http://cstheory.stackexchange.com/q/19213/), [Can relativization change the direction of separation?](http://cstheory.stackexchange.com/q/16268) I remember we had a question which was closer but couldn't find it, it might have got closed as off-topic automatically deleted by the software. Anyway Robin has answered the question quite nicely. :)
Kaveh
<cc.complexity-theory><oracles><relativization>
Is relativization well-defined?
Michael
# Is relativization well-defined?

(Asked by: username_0 on 2014-03-17)

According to BGS theorem [1], there is an oracle $A$ such that $P^A\neq NP^A$.

If the relativization operation $B\mapsto B^A$ was a well-defined function,
one would expect that from $B^A\neq C^A$ one would be able to conclude that $B\neq C$,
e.g. $P\neq NP$ would follow from BGS. However, $P\neq NP$ is still open.

Does that mean that relativization is not a well-defined function?

If so, do we have any example of two provably different relativizations of the same complexity class?

[1] T. P. Baker, J. Gill, and R. Solovay, "Relativizations of the P =? NP Question"

**Tags:** cc.complexity-theory, oracles, relativization

> **Comments:**
> **username_1**: Baker-Gill-Solovay shows two oracles: one where P and NP are equal and one where they aren't. That answers your last question.  
> **username_0**: @SureshVenkat: if you mean that there are oracles $A,B$ such that $P^A\neq NP^A$ and $P^B=NP^B$ then this result (Ladner's theorem?) is actually the background of my question. I can see why $P^B=NP^B$ does not imply $P=NP$, but I don't see why $P^A\neq NP^A$ does not imply $P\neq NP$.  
> **username_1**: @username_2 would be helpful to point to specific answers. I did a quick scan of the *questions* and didn't see anything.  
> **username_2**: PS: the short answer to your question is that a relativization is not an extensional/functional operator on class of problems, even if the notation looks to imply otherwise. There is no general definition of relativization for problem classes,  relativizations are defined for _machine models_ and a single machine model can have several different relativized versions.  
> **username_2**: pps: The example you are looking for is IP=PSpace provably but there are relativizations for IP and PSpace which are provably not equal, see [this question](http://cstheory.stackexchange.com/q/9934/186). If you want to read more about relativization you can start with Lance Fortnow's survey "[The role of relativization in complexity theory](http://www.cs.uchicago.edu/~fortnow/papers/relative.pdf)", 1994.  
> **username_3**: fyi fortnow notes/admits in his abstract that complexity theorists both use and _"misuse"_ relativization.... it seems to be an admittedly gray area of complexity theory _at times_....  
> **username_2**: @Suresh, I found these: [Techniques for proving that a sentence relativizes](http://cstheory.stackexchange.com/q/19213/), [Can relativization change the direction of separation?](http://cstheory.stackexchange.com/q/16268) I remember we had a question which was closer but couldn't find it, it might have got closed as off-topic automatically deleted by the software. Anyway Robin has answered the question quite nicely. :)  

---

## 1 answers

### Answer by username_4 on 2014-03-18. Score: 16 | Accepted answer

You are exactly right. The relativization operation $B\mapsto B^A$ is not well defined.
P and PA are independently defined objects. The names are suggestive, but you cannot formally define PA from the set P. (You can define P from PA by setting A to be the empty set.)

Think of PA as being some kind of generalization of P, which equals P when A is empty, but otherwise may be different. Now if you only know the set P, it is not clear how to generalize this to get PA. As an analogy, if I asked you to generalize the real numbers, it's not clear what generalization I'm looking for. Am I thinking of fields, rings, vector spaces, etc.? The reason this happens is that while P is merely a set of languages, PA is defined in terms of a machine. This machine has the property that when A is empty it decides exactly the same languages as P. You could come up with some other machine, let's call it QA, which also has the property that when A is empty decides the same languages as P. This does not mean that PA = QA for all A. This would be analogous to asserting that if f(0)=g(0), then f and g are the same function.

Perhaps [this post by Terence Tao](http://terrytao.wordpress.com/2009/08/01/pnp-relativisation-and-multiple-choice-exams/) will be helpful.

> **Comments:**
> **username_1**: Thanks, Robin. That's another good answer, and the link to Tao's article is very helpful.  

---

