<p>I think you need to redraw your Venn diagram... any containment of complexity classes which relativizes will also algebrize, at least in the sense of Aaronson and Wigderson. That is, access to the "low-degree extension" of an oracle is only more powerful than access to the oracle. Similarly, any oracles showing that a separation requires "non-algebrizing" techniques implies that "non-relativizing" techniques are also required.</p>

CC BY-SA 3.0
2012-04-15T05:32:56.867Z
I just saw this now... actually, Scott and Avi give several "algebrizing" implications too. Their notion is certainly defined in such a way as to subsume relativization. (For the implication Lance cites, they would probably say that the algebrizing implication is "$P^{\tilde{A}} = NP^{\tilde{A}}$ implies $PH^{A} \subseteq P^{\tilde{A}}$.")
Ryan Williams
CC BY-SA 4.0
2021-06-18T11:48:57.747Z
@RyanWilliams I think ACC0 vs NEXP is diagonalization correct?
Turbo
CC BY-SA 4.0
2021-06-19T13:30:40.857Z
Diagonalization is used in one part of the proof but there are other parts (such as the ACC SAT algorithm) which do not relativize or algebrize. The paper briefly explains why.
Ryan Williams
CC BY-SA 2.5
2010-09-17T00:44:05.940Z
Hi Ryan, I kept the diagram simple so that we can also discuss the "collapse" of these regions. For example, your answer can be restated as "$R \subseteq A$ in the sense of Aaronson-Wigderson".
Shiva Kintali
CC BY-SA 2.5
2010-11-19T12:13:24.653Z
What Ryan says holds only for containment. A result like P=NP implies P=PH relativizes but but doesn't algebrize.
Lance Fortnow
CC BY-SA 2.5
2010-11-30T06:25:16.003Z
@Lance : Thanks for clarifying. So, it makes sense to leave the diagram as it is.
Shiva Kintali
CC BY-SA 2.5
2010-09-17T00:10:08.923Z
2010-09-17T00:10:08.923Z
Ryan Williams
<p>Contrary to some claims earlier in this thread, algebrization in the sense of Aaronson &amp; Wigderson is not known to subsume relativization.  For example, </p>

<p>$$\tag{$\dagger$}(\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly})\implies \mathsf{NEXP} \not\subset \mathsf{P/poly}$$</p>

<p>is a statement that relativizes.  (In fact it has a relativizing proof, whatever that might mean to the reader.) But it is not known to algebrize, as alluded to by Aaronson &amp; Wigderson themselves in Section 10.1 of their paper [1].  (Consequently, while AW tells us that in the above diagram $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ must lie outside $\mathrm {A}$, it is conceivable that $\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly}$ lies inside!)</p>

<p>However, a recent work by Eric Bach and myself [2] gives a formulation of algebrization that does subsume relativization. Basically, if we take the AW notion of an algebraic oracle --- denoted as $\tilde O$  for some language $O$ --- and modify it wisely, then we can eliminate the pathologies such as $(\dagger)$ above. </p>

<p>The upshot is that algebrization, when suitably defined, is relativization with respect to an algebraic oracle --- an algebraic relativization, where every oracle gets a "wiggle'' --- which means $\mathrm{R} \setminus \mathrm{A}$ is the empty set in the above diagram, hence so is $\mathrm{RN}$.</p>

<p>[1] <a href="http://www.scottaaronson.com/papers/alg.pdf">http://www.scottaaronson.com/papers/alg.pdf</a><br>
[2] <a href="http://eccc.hpi-web.de/report/2016/040/">http://eccc.hpi-web.de/report/2016/040/</a></p>

<p>P.S.: Another formulation for algebrization was proposed by Impagliazzo, Kabanets and Kolokolova earlier, which also places $\mathrm{R}$ inside $\mathrm{A}$, but is not known to be as powerful as the AW notion. See my paper with Eric for a comparison.</p>

CC BY-SA 3.0
2016-07-17T05:41:18.317Z
Thanks Baris. I'm glad someone finally found the notion of algebrization which formally does what we think it should :)
Ryan Williams
CC BY-SA 3.0
2016-06-22T16:06:34.130Z
2016-06-22T16:33:34.747Z
2016-06-22T16:33:34.747Z
Barış Aydınlıoğlu
<p>The <em>time and space hierarchy theorems</em> relativize. 
They are uniform, so they don't seem to naturalize.</p>

<p>I think <em>indirect diagonalization results</em> like the TimeSpace lower bounds of Lance Fortnow, et al. and also Ryan Williams's result do not relativize 
because they are not black box (but I am not sure about this). 
The proofs don't seem to naturalize since they use hierarchy theorems.</p>

<p>The proofs of <em>permanent not in uniform $TC^0$</em> use hierarchy theorems and 
don't seem to work for nonuniform case, and doesn't seem to naturalize. 
On the other hand, I don't know if they relativize,
they may with a suitable notion of relativization.</p>

CC BY-SA 3.0
2010-09-17T02:22:43.370Z
2016-06-23T10:08:41.507Z
2016-06-23T10:08:41.507Z
Kaveh
<p>Interactive proofs do not relativize. I don't think they naturalize since they are uniform.  </p>

CC BY-SA 2.5
2010-09-16T23:57:39.703Z
2010-09-16T23:57:39.703Z
Suresh Venkat
<p>It is well known that any proof resolving the <a href="http://en.wikipedia.org/wiki/P_versus_NP_problem" rel="noreferrer">P vs NP</a> question must overcome <a href="http://kintali.wordpress.com/2009/09/01/relativization-barrier/" rel="noreferrer">relativization</a>, <a href="http://en.wikipedia.org/wiki/Natural_proof" rel="noreferrer">natural proofs</a> and <a href="http://portal.acm.org/citation.cfm?id=1374481" rel="noreferrer">algebrization</a> barriers. The following diagram partitions the "proof space" into different regions. For example, $RN$ corresponds to the set of proofs that relativize and naturalize. $GCT$ (Geometric Complexity Theory) is of course the strictly outside region.</p>

<p>Name some proofs along with the best known regions they belong to. Place them in a best possible way i.e., if a proof is known to relativize, naturalize and algebrize then it should be placed in $RNA$ not just in $RN$. If a proof relativizes but does not naturalize it belongs to $R$ ${\setminus}$ $N$ and so on.</p>

<p><img src="https://i.sstatic.net/ExWPB.jpg" alt="alt text"></p>

CC BY-SA 2.5
2010-09-16T23:55:10.830Z
But are there any known valid proofs of P _vs_ NP at all?
gphilip
CC BY-SA 2.5
2010-09-16T23:58:34.443Z
I do think this is a classic CW question though.
Suresh Venkat
CC BY-SA 2.5
2010-09-16T23:59:40.787Z
@gphilip We are talking about lower bound proofs in complexity theory in general.
Shiva Kintali
CC BY-SA 2.5
2010-09-17T00:07:12.697Z
@Suresh Placing proofs in these regions is highly non-trivial. People posting answers should be rewarded (by up votes of course) for their knowledge and understanding of these barriers. What do you think ?
Shiva Kintali
CC BY-SA 2.5
2010-09-17T00:08:55.930Z
After reading Suresh's answer below, I think I got the question (correct me if I am wrong) : you are looking for classifications of the form "If a proof that resolves P _vs_ NP has property X, then it belongs to region Y in the picture." In Suresh's answer X is "Interactive", and Y is outside R, possibly outside N as well.
gphilip
<cc.complexity-theory><proofs><barriers><p-vs-np>
Proofs, Barriers and P vs NP
Shiva Kintali
# Proofs, Barriers and P vs NP

(Asked by: username_0 on 2010-09-16)

It is well known that any proof resolving the [P vs NP](http://en.wikipedia.org/wiki/P_versus_NP_problem) question must overcome [relativization](http://kintali.wordpress.com/2009/09/01/relativization-barrier/), [natural proofs](http://en.wikipedia.org/wiki/Natural_proof) and [algebrization](http://portal.acm.org/citation.cfm?id=1374481) barriers. The following diagram partitions the "proof space" into different regions. For example, $RN$ corresponds to the set of proofs that relativize and naturalize. $GCT$ (Geometric Complexity Theory) is of course the strictly outside region.

Name some proofs along with the best known regions they belong to. Place them in a best possible way i.e., if a proof is known to relativize, naturalize and algebrize then it should be placed in $RNA$ not just in $RN$. If a proof relativizes but does not naturalize it belongs to $R$ ${\setminus}$ $N$ and so on.

![alt text](https://i.sstatic.net/ExWPB.jpg)

**Tags:** cc.complexity-theory, proofs, barriers, p-vs-np

> **Comments:**
> **username_1**: But are there any known valid proofs of P _vs_ NP at all?  
> **username_2**: I do think this is a classic CW question though.  
> **username_0**: @username_1 We are talking about lower bound proofs in complexity theory in general.  
> **username_0**: @Suresh Placing proofs in these regions is highly non-trivial. People posting answers should be rewarded (by up votes of course) for their knowledge and understanding of these barriers. What do you think ?  
> **username_1**: After reading Suresh's answer below, I think I got the question (correct me if I am wrong) : you are looking for classifications of the form "If a proof that resolves P _vs_ NP has property X, then it belongs to region Y in the picture." In Suresh's answer X is "Interactive", and Y is outside R, possibly outside N as well.  

---

## 4 answers

### Answer by username_3 on 2010-09-17. Score: 17

I think you need to redraw your Venn diagram... any containment of complexity classes which relativizes will also algebrize, at least in the sense of Aaronson and Wigderson. That is, access to the "low-degree extension" of an oracle is only more powerful than access to the oracle. Similarly, any oracles showing that a separation requires "non-algebrizing" techniques implies that "non-relativizing" techniques are also required.

> **Comments:**
> **username_0**: Hi Ryan, I kept the diagram simple so that we can also discuss the "collapse" of these regions. For example, your answer can be restated as "$R \subseteq A$ in the sense of Aaronson-Wigderson".  
> **username_5**: What Ryan says holds only for containment. A result like P=NP implies P=PH relativizes but but doesn't algebrize.  
> **username_0**: @Lance : Thanks for clarifying. So, it makes sense to leave the diagram as it is.  
> **username_3**: I just saw this now... actually, Scott and Avi give several "algebrizing" implications too. Their notion is certainly defined in such a way as to subsume relativization. (For the implication Lance cites, they would probably say that the algebrizing implication is "$P^{\tilde{A}} = NP^{\tilde{A}}$ implies $PH^{A} \subseteq P^{\tilde{A}}$.")  
> **username_4**: @RyanWilliams I think ACC0 vs NEXP is diagonalization correct?  
> **username_3**: Diagonalization is used in one part of the proof but there are other parts (such as the ACC SAT algorithm) which do not relativize or algebrize. The paper briefly explains why.  

---

### Answer by username_6 on 2016-06-22. Score: 14

Contrary to some claims earlier in this thread, algebrization in the sense of Aaronson & Wigderson is not known to subsume relativization. For example,

$$\tag{$\dagger$}(\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly})\implies \mathsf{NEXP} \not\subset \mathsf{P/poly}$$

is a statement that relativizes. (In fact it has a relativizing proof, whatever that might mean to the reader.) But it is not known to algebrize, as alluded to by Aaronson & Wigderson themselves in Section 10.1 of their paper [1]. (Consequently, while AW tells us that in the above diagram $\mathsf{NEXP} \not\subset \mathsf{P/poly}$ must lie outside $\mathrm {A}$, it is conceivable that $\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly}$ lies inside!)

However, a recent work by Eric Bach and myself [2] gives a formulation of algebrization that does subsume relativization. Basically, if we take the AW notion of an algebraic oracle --- denoted as $\tilde O$ for some language $O$ --- and modify it wisely, then we can eliminate the pathologies such as $(\dagger)$ above.

The upshot is that algebrization, when suitably defined, is relativization with respect to an algebraic oracle --- an algebraic relativization, where every oracle gets a "wiggle'' --- which means $\mathrm{R} \setminus \mathrm{A}$ is the empty set in the above diagram, hence so is $\mathrm{RN}$.

[1] <http://www.scottaaronson.com/papers/alg.pdf>  
[2] <http://eccc.hpi-web.de/report/2016/040/>

P.S.: Another formulation for algebrization was proposed by Impagliazzo, Kabanets and Kolokolova earlier, which also places $\mathrm{R}$ inside $\mathrm{A}$, but is not known to be as powerful as the AW notion. See my paper with Eric for a comparison.

> **Comments:**
> **username_3**: Thanks Baris. I'm glad someone finally found the notion of algebrization which formally does what we think it should :)  

---

### Answer by username_7 on 2010-09-17. Score: 11

The *time and space hierarchy theorems* relativize.
They are uniform, so they don't seem to naturalize.

I think *indirect diagonalization results* like the TimeSpace lower bounds of username_5, et al. and also username_3's result do not relativize
because they are not black box (but I am not sure about this).
The proofs don't seem to naturalize since they use hierarchy theorems.

The proofs of *permanent not in uniform $TC^0$* use hierarchy theorems and
don't seem to work for nonuniform case, and doesn't seem to naturalize.
On the other hand, I don't know if they relativize,
they may with a suitable notion of relativization.


---

### Answer by username_2 on 2010-09-16. Score: 7

Interactive proofs do not relativize. I don't think they naturalize since they are uniform.


---

