[Solved]: Why are non-relativizing proofs preferred to relativizing ones?

Problem Detail: I apologize, but even after these two other posts: here and here I’m still having trouble understanding oracle TMs and relativization. This question comes at the issue from a different angle: Why are non-relativizing proofs considered more valid than arguments based on relativized results? For example, we have a non-relativizing proof of IP = PSPACE, but couldn’t we just as well say an argument for the opposite by the fact that there exists an oracle separating them (I realize from an answer to a question I previously asked that this oracle exists due to a structural difference between the two complexity classes, but I see that as even more evidence that the classes are different in important ways and may not be equal). On the flip side, why do we conclude from the fact that there exist oracles $A$ and $B$ such that $P^A = NP^A$ and $P^B neq NP^B$ that non-relativizing techniques will be needed to resolve P vs. NP and not just resolve that oracles lead to inherent contradictions since we cannot have both P = NP and P $neq$ NP? Again, I realize from a previous post that we can view oracle TMs as different models of computation that can solve problems ordinary TMs cannot, but I see this as similar to the “theory of types tactic” used in Principia Mathematica which, according to my understanding, Godel (through the Incompleteness theorems) proved to be insufficient to resolving issues of the completeness and consistency of axiomatic systems.

Asked By : Ari

Answered By : Yuval Filmus

Let me try to answer your multifaceted question using an analogy from number theory (or rather, Peano arithmetic). The platonist point of view holds that every question about natural numbers has a YES/NO answer. This is known as “true arithmetic”. However, as Gödel showed, some propositions concerning natural numbers can be neither proved nor disproved. The platonist point of view still holds that these propositions have a definite truth value with respect to the “true” set of natural numbers; Gödel just showed that the no finite list of axioms1 can specify the true set of natural numbers. Let’s see what this implies regarding the P vs. NP question. The platonist point of view holds that either P=NP or P$neq$NP. It might be that P vs. NP is independent of the foundations of mathematics (say, ZFC), in which case we will be able to prove neither P=NP nor P$neq$NP. But according to most researchers, this possibility is unlikely. Therefore we would really like to know whether P=NP or not in the real world, which is the same as2 whether P=NP or not according to the standard foundations of mathematics. This is the research question. What about relativized models? Let me offer another analogy from number theory. If a polynomial identity is true over the integers then it is also true modulo $p$ for every prime $p$. So in order to disprove an identity, it is enough to show that it doesn’t hold for some $p$. We can think of the integers modulo $p$ as a “relativized model”. Let’s consider an example: $1 + 1 = 0$ modulo $2$ but not modulo $3$. Does it mean that we are no longer sure whether $1 + 1 = 0$ or not? Not at all. We know that $1 + 1 = 2$, and in particular $1 + 1 neq 0$. But in some relativized models, this equation fails to hold. The (informal) local-global principle states that in some situations, there is a set of “relativized models” which is complete for some number-theoretic statements. The classical example is quadratic forms: given a quadratic form $Q$ and a number $n$, then $Q$ represents $n$ over the rationals (that is, $n$ is in the image of $Q$ when the inputs are arbitrary rational numbers) iff it represents $n$ over the real numbers and the $p$-adics. Unfortunately, we have no similar theorems for complexity theory. In particular, given the truth value of relativized statements, we can deduce nothing about the original statement. The situation is even worse: it is not longer the case that a result true in the “true” world also holds relativized to any oracle. So we cannot even expect statements like the local-global principle to hold here. Something like “relativized techniques” also occurs in Peano arithmetic. There are statements regarding the natural numbers which can be proved in ZFC but not in Peano arithmetic. The classical examples are the Paris–Harrington theorem and Goodstein’s theorem. All proofs in Peano arithmetic are “relativizing” in the sense that they hold in all models of Peano arithmetic. The Paris–Harrington and Goodstein theorems fail in some non-standard models of Peano arithmetic, but these don’t represent true arithmetic; in true arithmetic the theorems hold. The problem is with Peano arithmetic rather than with the statements themselves: there are some properties of the natural numbers that it doesn’t describe, allowing these non-standard models to creep in. Gödel showed that this problem happens in all first-order models of arithmetic. Now we can address your questions:

  1. Why is a non-relativizing proof of IP=PSPACE preferred over oracle separations of the same two classes? We only care about the question IP=PSPACE? in the “true” world. It doesn’t matter what happens in relativized worlds. Since there exist oracles which separate IP and PSPACE, proofs of IP=PSPACE must be non-relativizing. The situation is analogous to the one involving the Paris–Harrington and Goodstein theorems. A different problem is that it is perhaps not clear how to define the relativized versions of these classes. This precludes presenting relativized results even as evidence.
  2. P=NP holds with respect to some oracle and fails to hold with respect to another; why do we conclude that non-relativizing techniques are needed rather than that oracles lead to inherent contradictions? This is the same as the situation of $1+1 neq 0$ above. This theorem is true, but has different truth values in different “relativized worlds” corresponding to the integers modulo $p$ for different values of $p$. This means that a proof of $1+1 neq 0$ must include some step that doesn’t hold modulo all $p$. It doesn’t mean that working modulo $p$ “leads to inherent contradictions”.
  3. Aren’t we seeing something similar in the “theory of types” developed in Principia Mathematica? The theory of types was developed as a consistent foundation for mathematics, after Russell discovered that naive set theory is inconsistent (using his paradox). No such foundational difficulties have been encountered in complexity theory.
  4. What are the implications of Gödel’s incompleteness theorem? The incompleteness theorem raises the possibility that P vs. NP is independent of the current foundations of mathematics. But this is considered unlikely by most researchers. Many difficult theorems have been proved in the past; some of them had been open for centuries (for example Fermat’s last theorem). The fact that a theorem is difficult is no reason to think that it is beyond solution.

This leaves one question which you haven’t asked: Why do we care about relativized results? I don’t know the historical reason. It might be that these techniques are commonplace in related ares that served as sources of inspiration. At the very beginning, people might have expected that relativized results do imply absolute results. A good example is the random oracle hypothesis, which states that if a complexity theory statement holds with respect to a random oracle, then it holds absolutely. For example, although the P vs. NP is “undecided” with respect to an arbitrary oracle, Baker, Gill and Solovay showed that P$neq$NP with respect to a random oracle. Does that imply that P$neq$NP? The fact that IP=PSPACE disproved this hypothesis. Since that point, much less attention has been given to oracle results, and they are now quite unfashionable. They have become an object of study in their own right, but with no pretensions to be relevant for separating P from NP. Endnotes:

  1. The usual axiomatization of Peano arithmetic actually uses a finite number of axiom schemes. Gödel’s result holds in even greater generality, as Andrej Bauer indicates in his thoughtful comments.
  2. See Andrej Bauer’s comments for a dissenting opinion.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/34005

Leave a Reply