10
$\begingroup$

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"

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ Baker-Gill-Solovay shows two oracles: one where P and NP are equal and one where they aren't. That answers your last question. $\endgroup$
    – Suresh Venkat
    Commented Mar 17, 2014 at 18:27
  • $\begingroup$ @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$. $\endgroup$
    – Michael
    Commented Mar 17, 2014 at 18:35
  • 2
    $\begingroup$ @Kaveh would be helpful to point to specific answers. I did a quick scan of the questions and didn't see anything. $\endgroup$
    – Suresh Venkat
    Commented Mar 17, 2014 at 20:55
  • 4
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Mar 17, 2014 at 21:40
  • 1
    $\begingroup$ 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.... $\endgroup$
    – vzn
    Commented Mar 18, 2014 at 15:34

2 Answers 2

Reset to default
16
$\begingroup$

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 will be helpful.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, Robin. That's another good answer, and the link to Tao's article is very helpful. $\endgroup$
    – Suresh Venkat
    Commented Mar 18, 2014 at 18:08
5
$\begingroup$

(I assume this question will eventually get migrated to CS.SE, but I am posting my answer to it here on cstheory for now.)

Technically, one doesn't usually think of relativization as an "operator" or "function"; however, I don't see a reason why you couldn't take a statement and map the statement to a relativized version of it.

The trick is that, as others have said, relativization isn't really defined over a complexity class; instead, it is defined on the computation model you are using. Further, what relativizes is the statement, not the classes. (The notation is a little misleading.)

An example of this is that I could theoretically say that a statement relativizes (or, less likely, doesn't relativize) even if it doesn't refer to a Turing machine at all. E.g., I could say (truthfully), "1 + 1 = 2" relativizes, because relative to every oracle that could be added to the definition of my universal Turing machine, 1 + 1 = 2 would remain true.

So the short answer is: Yes, it's well-defined, but not on classes.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ I think for me personally, (and maybe for the OP) the question is: suppose we take the proof that $P^A \ne NP^A$. If $P = NP$, it "appears" to be nonsensical to take the oracle $A$ used in the construction and demonstrate the inequality since the two underlying classes are equal. But clearly it's possible, and so where is my mistake ? $\endgroup$
    – Suresh Venkat
    Commented Mar 18, 2014 at 0:09
  • 2
    $\begingroup$ That's what I was getting at in my answer...I said, you can't relativize over classes, you relativize over statements. The ability to relativize over P and NP goes away if you cannot relativize over classes individually; the argument doesn't work if I just say "I relativized a statement, now invert the relativization and it should still hold" any more than it's possible to say (using the function f(x) = x^2 as an example) "5^2 is composite" --> "5 is composite." $\endgroup$
    – user1338
    Commented Mar 18, 2014 at 1:11
  • 3
    $\begingroup$ There is no general definition of relativization of statements. There is only relativized models of computation. The relativization of P vs. NP presumes that we have fixed the relativized models of P and NP beforehand. $\endgroup$
    – Kaveh
    Commented Mar 18, 2014 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.