18
$\begingroup$

I am afraid this post may show my naivety. At a recent conference, someone told me that there are some arguments in computability theory that don't relativize. Unfortunately, this person (who I think may be an MO regular) couldn't give me any examples off-hand.

My naive understanding is that one can take any proof, fix an oracle and replace "Turing machine" with "Turing machine using that oracle". (Similarly, replace "computable" with "computable w.r.t. this oracle" and so on.) But I am probably missing something.

So is it possible to relativize any proof? Is it not possible? Or is it technically possible to relativize any proof, but the relativization isn't what you may expect?

If it is not always possible, can someone provide me a good example or reference? Also, any discussion on what makes a proof relativizable or not would be of help.

Actually, while writing this, I may have come up with an example. It's known that $P=NP$ and $P \neq NP$ for different oracles. But this is a relativization of a theorem (conjecture), not it's proof. So this brings up related questions. Is relativizing the statement of a theorem different from relativizing the proof? What if the theorem/proof has nothing to do with the actual model of computation (e.g. the proof doesn't refer to ideas such as time-complexity, only computability)?

Thanks!

$\endgroup$
6
  • $\begingroup$ You might get better answers at cstheory.stackexchange.com . $\endgroup$ Feb 19, 2011 at 0:46
  • 2
    $\begingroup$ I also don't really understand the question. Certainly you can go through a proof and relativize all the terms in it, but what guarantees that the resulting proof is valid? Your last paragraph seems to already answer your question: if one day we knew that P=NP (for the sake of argument) and a proof used the step "since P=NP," then relativizing with respect to an oracle for which P \neq NP is obviously not valid. $\endgroup$ Feb 19, 2011 at 1:19
  • 2
    $\begingroup$ Here's a silly example showing why this is usually interpreted in terms of homogeneity, in the context of Turing degrees, as Andrew Marks indicated. There is no computable completion of Peano artithmetic, but for some degrees $A$ there is an $A$-computable completion of Peano Arithmetic (e.g. $A = 0'$). The thing is that "Peano arithmetic" and "completion" are absolute in some way, they don't change if we move to a degree $A$. One way to avoid this is to look only at statements in the language $(<, ')$ of the Turing degree lattice. At least all these statements have a hope of relativizing. $\endgroup$ Feb 19, 2011 at 12:36
  • 1
    $\begingroup$ @Carl, This is indeed a nice example. I can see exactly what goes wrong. PA encodes all Turing machines. Knowing a completion of PA solves the halting problem for each encoded machine (I think!). But computing the completion relative to an oracle doesn't give the encoded Turning machines access to this oracle. If, however, we added a function to the language of PA and hard coded the oracle into the function by adding axioms, then any completion of PA with these new axioms is not computable relative to the oracle. This is making me believe relativization is more of an art. $\endgroup$
    – Jason Rute
    Feb 19, 2011 at 16:01
  • 1
    $\begingroup$ Question asked on CSTheory has some more info: cstheory.stackexchange.com/questions/20511/… $\endgroup$
    – Sai
    Jan 9, 2014 at 16:48

2 Answers 2

23
$\begingroup$

Early in the history of recursion theory, the realization that all known proofs in the subject could be relativized in the manner you indicate led Hartley Rogers to make what is called the homogeneity conjecture.

Let $\mathcal{D}$ be the structure of the Turing degrees with the partial order of Turing reducibility $\leq_T$. Let $\mathcal{D}(\geq \mathbf{x})$ be the structure of the Turing degrees that are $\geq_T \mathbf{x}$ also with the partial order $\leq_T$. The homogeneity conjecture says that for any Turing degree $\mathbf{x}$, $\mathcal{D}$ is isomorphic to $\mathcal{D}(\geq \mathbf{x})$.

Richard Shore refuted the homogeneity conjecture in an elegant 1979 paper -- it's only one page long (though it relies on earlier work coding models of arithmetic in $\mathcal{D}$). A couple years later, Harrington and Shore showed that you can do even better. Not only are there Turing degrees $\mathbf{x}$ for which $\mathcal{D}$ and $\mathcal{D}(\geq \mathbf{x})$ aren't isomorphic as structures, there are Turing degrees $\mathbf{x}$ so that $\mathcal{D}$ and $\mathcal{D}(\geq \mathbf{x})$ aren't elementarily equivalent.

So this means that there is a first order sentence $\varphi$ in the language only containing $\leq_T$ which is true about the Turing degrees, but which is false if you relativize the sentence to the Turing degrees $\geq_T \mathbf{x}$ for some $\mathbf{x}$ (and of course, working in the Turing degrees $\geq_T \mathbf{x}$ is equivalent to giving all Turing machines access to $\mathbf{x}$ as an oracle). Hence, the proof that $\varphi$ is true can't be relativized to $\mathbf{x}$.

A somewhat misleading and oversimplified explanation of why this occurs is that you can code models of arithmetic into $\mathcal{D}$ (or $\mathcal{D}(\geq \mathbf{x})$) which can then interpret unrelativized concepts like being arithmetically definable or hyperarithmetically definable.

A particularly spectacular form of this phenomenon would occur if Slaman and Woodin's biinterpertability conjecture is true. The conjecture says that the following relation (on $\overrightarrow{\mathbf{p}}$ and $\mathbf{d}$) is definable in $\mathcal{D}$: "$\overrightarrow{\mathbf{p}}$ codes a standard model of first order arithmetic and a real $X$ such that $X$ is of degree $\mathbf{d}$".

All that being said, just about every proof in recursion theory that I know of relativizes. I'd be very interested in a proof which doesn't relativize and doesn't factor through the coding machinery I've mentioned above.

By the way (and somewhat ironically), the Baker-Gill-Solovay theorem that you mentioned does itself relativize. The relativized version says that for any oracle $X$, there are oracles $A$ and $B$ so that $X$ is poly-time reducible to both $A$ and $B$, and $P^A = NP^A$ and $P^B \neq NP^B$. (We've relativized to $X$ here. The unrelativized result simply says that there are oracles $A$ and $B$ so that $P^A = NP^A$ and $P^B \neq NP^B$). Of course, the real point is that a proof that $P \neq NP$ can't use a technique that relativizes.

$\endgroup$
1
  • $\begingroup$ This is exactly what I was looking for. Thanks! $\endgroup$
    – Jason Rute
    Feb 19, 2011 at 16:08
4
$\begingroup$

(Note: I have probably misunderstood your question!)

Here's one example that is, along with the nonrelativization of $\mathbf{P}$ versus $\mathbf{NP}$, standard: The proof that $\mathbf{IP} = \mathbf{PSPACE}$ does not relativize, since for almost all oracles $A$, we have that $\mathbf{IP}^A\neq \mathbf{PSPACE}^A$, but they are equal under, for instance, the empty oracle.

$\endgroup$

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.