7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You say "relativizing arguments"; do you actually mean "arguments using relativization" or "arguments about relativized classes" instead? $\endgroup$ – user12859 Dec 8 '14 at 2:52
  • $\begingroup$ @Ricky Sorry that I was unclear. I meant both arguments based on relativization results and methods which relativize (e.g. diagonaLization)? $\endgroup$ – Ari Dec 8 '14 at 2:57
  • $\begingroup$ "For example, we have" that $\;\; 6+7 \: = \: 13 \;\;$, $\;\;$ "but couldn't we just as well say an argument for the opposite by the fact that there exists" a base "separating them"? $\;\;\;\;\;\;$ $\endgroup$ – user12859 Dec 8 '14 at 3:22
  • 4
    $\begingroup$ Oracles don't lead to inherent contradictions. The fact that there are oracles $A$ and $B$ s.t. $P^A=NP^A$ but $P^B\neq NP^B$ doesn't mean that $P=NP$ and $P\neq NP$. It means that there are super-powers that you can add to Turing machines so that the things you can do deterministically in polytime are the same as the things you can do nondeterministically, and that there are other super-powers you can add such that a nondeterministic machine can do more. $\endgroup$ – David Richerby Dec 8 '14 at 9:08
  • 1
    $\begingroup$ This may be addressed here. $\endgroup$ – Raphael Dec 8 '14 at 11:49
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your well thought out and in depth answer. I'm just still confused over the analogy between modular arithmetic and relativization results but I guess it's just bordering on the philosophical end: Theorems dealing with natural numbers address issues in a "Platonic reality" whereas I feel that TCS should be more closely tied to models which we can actually build in the "real world" and, to me at least, oracle TMs fall out of that realm. Of course even ordinary TMs are just a theoretical model (since they have an infinite tape) so I guess I should just get used to it. $\endgroup$ – Ari Dec 9 '14 at 3:21
  • $\begingroup$ It is most definitely not a formalist point of view that every question has a yes/no answer. That would be a Platonist or a realist view. The formalist view is that it's all just a game in which we push some symbols around. $\endgroup$ – Andrej Bauer Dec 9 '14 at 11:15
  • $\begingroup$ Furthermore, Gödel did not show just that finite lists of axioms are insufficient, but that any primitive recursive set of axioms is insufficient. After all, Peano's axioms are infinitely many because one of them is a schema, so that's already infinitely many axioms right there. $\endgroup$ – Andrej Bauer Dec 9 '14 at 11:17
  • $\begingroup$ It is a mistake to equate "the real world" with "foundations of mathematics". $\endgroup$ – Andrej Bauer Dec 9 '14 at 11:18
  • $\begingroup$ After reading this answer, I think the answer would be much improved if the first two paragraphs are deleted. They are hardly related to the rest of the answer, and they are rife with mistakes and inaccuracies. $\endgroup$ – Andrej Bauer Dec 9 '14 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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