# Proofs, Barriers and P vs NP

It is well known that any proof resolving the P vs NP question must overcome relativization, natural proofs and algebrization 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.

• But are there any known valid proofs of P vs NP at all? – gphilip Sep 16 '10 at 23:55
• I do think this is a classic CW question though. – Suresh Venkat Sep 16 '10 at 23:58
• @gphilip We are talking about lower bound proofs in complexity theory in general. – Shiva Kintali Sep 16 '10 at 23:59
• @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 Sep 17 '10 at 0:07
• 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 Sep 17 '10 at 0:08

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.

• 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 Sep 17 '10 at 0:44
• What Ryan says holds only for containment. A result like P=NP implies P=PH relativizes but but doesn't algebrize. – Lance Fortnow Nov 19 '10 at 12:13
• @Lance : Thanks for clarifying. So, it makes sense to leave the diagram as it is. – Shiva Kintali Nov 30 '10 at 6:25
• 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 Apr 15 '12 at 5:32

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}$.

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.

• Thanks Baris. I'm glad someone finally found the notion of algebrization which formally does what we think it should :) – Ryan Williams Jul 17 '16 at 5:41

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 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.

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.

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