Asked By : Ari
Answered By : Yuval Filmus
- 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.
- 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”.
- 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.
- 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:
- 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.
- See Andrej Bauer’s comments for a dissenting opinion.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/34005