25
$\begingroup$

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.

alt text

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

4 Answers 4

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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". $\endgroup$
    – Shiva Kintali
    Sep 17, 2010 at 0:44
  • 4
    $\begingroup$ What Ryan says holds only for containment. A result like P=NP implies P=PH relativizes but but doesn't algebrize. $\endgroup$
    – Lance Fortnow
    Nov 19, 2010 at 12:13
  • $\begingroup$ @Lance : Thanks for clarifying. So, it makes sense to leave the diagram as it is. $\endgroup$
    – Shiva Kintali
    Nov 30, 2010 at 6:25
  • 3
    $\begingroup$ 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}}$.") $\endgroup$
    – Ryan Williams
    Apr 15, 2012 at 5:32
  • $\begingroup$ @RyanWilliams I think ACC0 vs NEXP is diagonalization correct? $\endgroup$
    – Turbo
    Jun 18, 2021 at 11:48
14
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Baris. I'm glad someone finally found the notion of algebrization which formally does what we think it should :) $\endgroup$
    – Ryan Williams
    Jul 17, 2016 at 5:41
11
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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