<p>As Steven notes, the canonical example is $\mathsf{IP} = \mathsf{PSPACE}$. This collapse does not relativize, in the sense that there is an oracle $A$, subject to which $\mathsf{IP}^A \ne \mathsf{PSPACE}^A$. The intuition why the known proof of this result avoids the relativization barrier is that it uses arithmetization (Yonatan alluded to this in a comment): an interactive protocol for the $\mathsf{PSPACE}$-complete problem TQBF is given by considering an extension of a quantified boolean formula to a low-degree polynomial over a suitably large field. If we are given a relativized boolean formula (with oracle gates), such an extension does not exist. </p>

<p>There is a refinement of the relativization barrier -- algebrization -- due to <a href="http://www.scottaaronson.com/papers/alg.pdf">Aaronson and Wigderson</a>. Generically, the arithmetization technique is not enough to circumvent the algebrization barrier. A complexity class inclusion $\mathsf{C} \subseteq \mathsf{D}$ algebrizes if for any oracle $A$ and any extension $\tilde{A}$ of $A$ to low-degree polynomials over a finite field, $\mathsf{C}^A \subseteq \mathsf{D}^{\tilde{A}}$. A separation $\mathsf{C} \not \subset \mathsf{D}$ algebrizes if for all $A$, and all extensions $\tilde{A}$, $\mathsf{C}^{\tilde{A}} \not \subset \mathsf{D}^{A}$. Aaronson and Wigderson show that $\mathsf{IP} = \mathsf{PSPACE}$ algebrizes, but many other results, including $\mathsf{NP} \not \subset \mathsf{P}$, do not.</p>

<p>A recent example of a technique that does not algebrize or relativize is <a href="http://www.stanford.edu/~rrwill/acc-lbs.pdf">Ryan Williams' proof</a> that $\mathsf{NEXP} \not \subset \mathsf{ACC}$. The separation does not algebrize: there is an oracle $A$ and a low-degree extension $\tilde{A}$ such that $\mathsf{NEXP}^{\tilde{A}} \subset \mathsf{ACC}^A$.  Intuitively the reason why the proof avoids the barrier is that it relies on the existence of a faster-than-trivial satisfiability algorithm for $\mathsf{ACC}$ circuits, and the algorithm uses non-relativizing and non-algebrizing properties of such circuits. Ryan notes in the paper that all known faster-than-trivial satisfiability algorithms break down when oracles or algebraic extensions of oracles are added.</p>

<p>There is also an interesting approach to understanding relativization through logic. In an old manuscript, <a href="http://www.cs.berkeley.edu/~vazirani/pubs/relativizing.ps">Arora, Impagliazzo, and Vazirani</a> define a system of axioms such that the relativizing results are exactly those that follow from the axioms, while non-relativizing results are independent from the system. A paper by <a href="http://www.cs.sfu.ca/~kabanets/papers/act-full.pdf">Impagliazzo, Kabanets, and Kolokolova</a> does something similar for algebrization by introducing an additional axiom to the ones defined by Arora, Impagliazzo and Vazirani. They show that most known non-relativizing results follow from their axioms, while P vs NP, among others, is independent of them.</p>

<p>Apologies if I got something wrong, I am not quite an expert.</p>

CC BY-SA 3.0
2014-01-09T16:14:54.643Z
There are other examples on non-relativizing proofs in the Aaronson-Wigderson paper, such as $\textrm{NEXP} \subseteq  \textrm{MIP}$, $\textrm{MA}_\textrm{EXP} \nsubseteq \textrm{P}/\textrm{poly}$, $\textrm{PromiseMA} \nsubseteq \textrm{SIZE}(n^k)$, etc.
Robin Kothari
CC BY-SA 3.0
2014-01-09T11:45:54.287Z
2014-01-27T16:36:15.847Z
2014-01-27T16:36:15.847Z
Sasho Nikolov
<p>this is a nice survey of the field by a leading expert that summarizes/details some of the points of the other answers so far &amp; has additional examples.</p>

<p>[1] <a href="http://people.cs.uchicago.edu/~fortnow/papers/relative.pdf">The Role of Relativization in Complexity Theory</a> Fortnow</p>

<blockquote>
  <p>Several recent nonrelativizing results in the area of interactive proofs have caused many
  people to review the importance of relativization. In this paper we take a look at how complexity
  theorists use and misuse oracle results. We pay special attention to the new interactive proof
  systems and program checking results and try to understand why they do not relativize. We
  give some new results that may help us to understand these questions better.</p>
</blockquote>

CC BY-SA 3.0
2014-01-10T17:05:11.920Z
+1 this is a nice survey, but it should be mentioned that it surveys the state of the world *up to 1993*
Sasho Nikolov
CC BY-SA 3.0
2014-01-10T18:49:24.570Z
true; it would be helpful if authors included dates in their papers more... a more recent survey would be helpful too, the topic seems rarely surveyed. this area does not seem to change so much & its not so clear how many new results have emerged since that date.
vzn
CC BY-SA 3.0
2014-01-10T19:14:55.517Z
for new results: I think some new oracle results have appeared since that relate to quantum complexity classes. more importantly, there have been developments in terms of what oracle results mean: the algebrization barrier and Ryan's non-algebrizing proof from my answer, a related paper http://www.cs.sfu.ca/~kabanets/papers/act-full.pdf, and possibly Boaz Barak's work on non-black-box reductions in crypto.
Sasho Nikolov
CC BY-SA 3.0
2014-01-10T16:14:52.883Z
2014-01-10T16:14:52.883Z
vzn
<p>As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles).</p>

<p>Virtually all proofs seem to be relativizable, though.</p>

<p>What are good examples of <em>non</em> relativizable proofs, of the sort that a P=NP/P≠NP proof would need to be, that are not trivial or contrived?</p>

<p>(I am not a recursion theorist, so please pardon the lack of citations.)</p>

<p>[EDIT: better <a href="https://mathoverflow.net/questions/55933/what-proofs-cannot-be-relativized">mathoverflow</a> post]</p>

CC BY-SA 3.0
2014-01-09T06:08:09.157Z
To copy over my suggestion from MO and get it out of the way: the canonical example I'm aware of is the proof of IP=PSPACE, where particularly the inclusion of PSPACE in IP is done by showing an interactive proof for a particular PSPACE-complete problem, a non-relativizable technique - particular problems don't relativize.
Steven Stadnicki
CC BY-SA 3.0
2014-01-09T07:07:21.790Z
@Steven: but can the proof be adapted easily to the relativized version?
Andrej Bauer
CC BY-SA 3.0
2014-01-09T07:19:17.837Z
@AndrejBauer AFAIK, no, because there's no such thing as 'relativized TQBF' - in fact, there are oracles $A$ with $\mathrm{IP}^A\neq \mathrm{PSPACE}^A$, so the proof can't canonically relativize.
Steven Stadnicki
CC BY-SA 3.0
2014-01-09T08:12:53.857Z
@RickyDemer Even still, the heart of the proof works by interpreting the formula as a low-degree polynomial, which doesn't carry through when you have (say) a uniformly random oracle gate.
Yonatan N
CC BY-SA 3.0
2014-01-09T12:56:25.137Z
Even though the question is on-topic here, crossposting was a bad suggestion, as it's [against site policy](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231). The problem is that it fragments answers, even though you've done the right thing to minimize that by linking between the two questions. For example, somebody has commented on MO that the question seems to be a duplicate of an existing question but this information hasn't been posted here. Migration is the best option.
David Richerby
CC BY-SA 3.0
2014-01-09T16:55:32.250Z
@DavidRicherby I don't know how to migrate. I did change the cross-pointer to the previous MO post.
Sai
CC BY-SA 3.0
2014-01-09T20:18:58.247Z
@Sai To migrate, click the flag link just below the list of tags and ask a moderator to do it.
David Richerby
CC BY-SA 3.0
2014-01-10T18:56:19.897Z
btw the P=?NP result on relativization is known as the [Baker-Gill-Solovay 1975](http://zoo.cs.yale.edu/classes/cs468/BGS.pdf) theorem. the proof can also be found eg in [Hopcroft/Ullman](http://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation). @richerby/Sai there is no reason to migrate after both questions are already entered, its more for future reference. also note there seems to be no official stackexchange cross-site policy on crossposting (hence some confusion is understandable).
vzn
CC BY-SA 3.0
2014-01-10T19:51:05.757Z
here is another writeup of [BGS75 by Katz](http://www.cs.umd.edu/~jkatz/complexity/f05/relativization.pdf) with more refs.
vzn
<cc.complexity-theory><lo.logic><computability><p-vs-np><relativization>
What are natural examples of non-relativizable proofs?
Sai
# What are natural examples of non-relativizable proofs?

(Asked by: username_0 on 2014-01-09)

As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles).

Virtually all proofs seem to be relativizable, though.

What are good examples of *non* relativizable proofs, of the sort that a P=NP/P≠NP proof would need to be, that are not trivial or contrived?

(I am not a recursion theorist, so please pardon the lack of citations.)

[EDIT: better [mathoverflow](https://mathoverflow.net/questions/55933/what-proofs-cannot-be-relativized) post]

**Tags:** cc.complexity-theory, lo.logic, computability, p-vs-np, relativization
> **Comments:**
> **username_1**: To copy over my suggestion from MO and get it out of the way: the canonical example I'm aware of is the proof of IP=PSPACE, where particularly the inclusion of PSPACE in IP is done by showing an interactive proof for a particular PSPACE-complete problem, a non-relativizable technique - particular problems don't relativize.  
> **username_2**: @Steven: but can the proof be adapted easily to the relativized version?  
> **username_1**: @AndrejBauer AFAIK, no, because there's no such thing as 'relativized TQBF' - in fact, there are oracles $A$ with $\mathrm{IP}^A\neq \mathrm{PSPACE}^A$, so the proof can't canonically relativize.  
> **username_3**: @RickyDemer Even still, the heart of the proof works by interpreting the formula as a low-degree polynomial, which doesn't carry through when you have (say) a uniformly random oracle gate.  
> **username_4**: Even though the question is on-topic here, crossposting was a bad suggestion, as it's [against site policy](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231). The problem is that it fragments answers, even though you've done the right thing to minimize that by linking between the two questions. For example, somebody has commented on MO that the question seems to be a duplicate of an existing question but this information hasn't been posted here. Migration is the best option.  
> **username_0**: @DavidRicherby I don't know how to migrate. I did change the cross-pointer to the previous MO post.  
> **username_4**: @Sai To migrate, click the flag link just below the list of tags and ask a moderator to do it.  
> **username_5**: btw the P=?NP result on relativization is known as the [Baker-Gill-Solovay 1975](http://zoo.cs.yale.edu/classes/cs468/BGS.pdf) theorem. the proof can also be found eg in [Hopcroft/Ullman](http://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation). @richerby/Sai there is no reason to migrate after both questions are already entered, its more for future reference. also note there seems to be no official stackexchange cross-site policy on crossposting (hence some confusion is understandable).  
> **username_5**: here is another writeup of [BGS75 by Katz](http://www.cs.umd.edu/~jkatz/complexity/f05/relativization.pdf) with more refs.  

---

## 2 answers

### Answer by username_6 on 2014-01-09. Score: 26

As Steven notes, the canonical example is $\mathsf{IP} = \mathsf{PSPACE}$. This collapse does not relativize, in the sense that there is an oracle $A$, subject to which $\mathsf{IP}^A \ne \mathsf{PSPACE}^A$. The intuition why the known proof of this result avoids the relativization barrier is that it uses arithmetization (Yonatan alluded to this in a comment): an interactive protocol for the $\mathsf{PSPACE}$-complete problem TQBF is given by considering an extension of a quantified boolean formula to a low-degree polynomial over a suitably large field. If we are given a relativized boolean formula (with oracle gates), such an extension does not exist.

There is a refinement of the relativization barrier -- algebrization -- due to [Aaronson and Wigderson](http://www.scottaaronson.com/papers/alg.pdf). Generically, the arithmetization technique is not enough to circumvent the algebrization barrier. A complexity class inclusion $\mathsf{C} \subseteq \mathsf{D}$ algebrizes if for any oracle $A$ and any extension $\tilde{A}$ of $A$ to low-degree polynomials over a finite field, $\mathsf{C}^A \subseteq \mathsf{D}^{\tilde{A}}$. A separation $\mathsf{C} \not \subset \mathsf{D}$ algebrizes if for all $A$, and all extensions $\tilde{A}$, $\mathsf{C}^{\tilde{A}} \not \subset \mathsf{D}^{A}$. Aaronson and Wigderson show that $\mathsf{IP} = \mathsf{PSPACE}$ algebrizes, but many other results, including $\mathsf{NP} \not \subset \mathsf{P}$, do not.

A recent example of a technique that does not algebrize or relativize is [Ryan Williams' proof](http://www.stanford.edu/~rrwill/acc-lbs.pdf) that $\mathsf{NEXP} \not \subset \mathsf{ACC}$. The separation does not algebrize: there is an oracle $A$ and a low-degree extension $\tilde{A}$ such that $\mathsf{NEXP}^{\tilde{A}} \subset \mathsf{ACC}^A$. Intuitively the reason why the proof avoids the barrier is that it relies on the existence of a faster-than-trivial satisfiability algorithm for $\mathsf{ACC}$ circuits, and the algorithm uses non-relativizing and non-algebrizing properties of such circuits. Ryan notes in the paper that all known faster-than-trivial satisfiability algorithms break down when oracles or algebraic extensions of oracles are added.

There is also an interesting approach to understanding relativization through logic. In an old manuscript, [Arora, Impagliazzo, and Vazirani](http://www.cs.berkeley.edu/~vazirani/pubs/relativizing.ps) define a system of axioms such that the relativizing results are exactly those that follow from the axioms, while non-relativizing results are independent from the system. A paper by [Impagliazzo, Kabanets, and Kolokolova](http://www.cs.sfu.ca/~kabanets/papers/act-full.pdf) does something similar for algebrization by introducing an additional axiom to the ones defined by Arora, Impagliazzo and Vazirani. They show that most known non-relativizing results follow from their axioms, while P vs NP, among others, is independent of them.

Apologies if I got something wrong, I am not quite an expert.

> **Comments:**
> **username_7**: There are other examples on non-relativizing proofs in the Aaronson-Wigderson paper, such as $\textrm{NEXP} \subseteq  \textrm{MIP}$, $\textrm{MA}_\textrm{EXP} \nsubseteq \textrm{P}/\textrm{poly}$, $\textrm{PromiseMA} \nsubseteq \textrm{SIZE}(n^k)$, etc.  

---

### Answer by username_5 on 2014-01-10. Score: 7

this is a nice survey of the field by a leading expert that summarizes/details some of the points of the other answers so far & has additional examples.

[1] [The Role of Relativization in Complexity Theory](http://people.cs.uchicago.edu/~fortnow/papers/relative.pdf) Fortnow

> Several recent nonrelativizing results in the area of interactive proofs have caused many
> people to review the importance of relativization. In this paper we take a look at how complexity
> theorists use and misuse oracle results. We pay special attention to the new interactive proof
> systems and program checking results and try to understand why they do not relativize. We
> give some new results that may help us to understand these questions better.

> **Comments:**
> **username_6**: +1 this is a nice survey, but it should be mentioned that it surveys the state of the world *up to 1993*  
> **username_5**: true; it would be helpful if authors included dates in their papers more... a more recent survey would be helpful too, the topic seems rarely surveyed. this area does not seem to change so much & its not so clear how many new results have emerged since that date.  
> **username_6**: for new results: I think some new oracle results have appeared since that relate to quantum complexity classes. more importantly, there have been developments in terms of what oracle results mean: the algebrization barrier and Ryan's non-algebrizing proof from my answer, a related paper http://www.cs.sfu.ca/~kabanets/papers/act-full.pdf, and possibly Boaz Barak's work on non-black-box reductions in crypto.  

---

