Preuves, barrières et P vs NP

Il est bien connu que toute preuve résolvant la question P vs NP doit surmonter la relativisation , les preuves naturelles et les barrières d' algèbre . Le diagramme suivant partitionne "l'espace de preuve" en différentes régions. Par exemple, correspond à l'ensemble des preuves qui relativisent et naturalisent. (théorie de la complexité géométrique) est bien sûr la région strictement extérieure.G C $RN$$GCT$

Nommez quelques preuves ainsi que les régions les plus connues auxquelles elles appartiennent. Placez-les de la meilleure façon possible, c'est-à-dire que si une preuve est connue pour relativiser, naturaliser et algébrize, elle doit être placée dans l' pas seulement dans la . Si une preuve relativise mais ne se naturalise pas, elle appartient à et ainsi de suite.R N R ∖$RNA$$RN$$R$ ${\setminus}$ $N$

Je pense que vous devez redessiner votre diagramme de Venn ... tout confinement des classes de complexité qui relativise sera également algébrize, au moins dans le sens d'Aaronson et Wigderson. C'est-à-dire que l'accès à "l'extension de bas degré" d'un oracle n'est que plus puissant que l'accès à l'oracle. De même, tout oracle montrant qu'une séparation nécessite des techniques "non algébriantes" implique que des techniques "non relativisantes" sont également nécessaires.

Contrairement à certaines affirmations antérieures de ce fil, l'algèbre au sens d'Aaronson & Wigderson n'est pas connue pour subsumer la relativisation. Par exemple,

est une déclaration qui relativise. (En fait, il a une preuve relativisante, quoi que cela puisse signifier pour le lecteur.) Mais il n'est pas connu pour algebrize, comme fait allusion à Aaronson & Wigderson eux-mêmes dans la section 10.1 de leur article [1]. (Par conséquent, même si AW nous indique que dans le diagramme ci-dessus, doit se trouver en dehors de , il est concevable que se trouve à l'intérieur!)A ∃ C : C ⊂ N E X P ∧ C ⊄ P / p o l $\mathsf{NEXP} \not\subset \mathsf{P/poly}$$\mathrm {A}$$\exists \mathcal{C}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly}$

Cependant, un travail récent d'Eric Bach et de moi-même [2] donne une formulation d'algèbre qui subsume la relativisation. Fondamentalement, si nous prenons la notion AW d'un oracle algébrique --- noté pour une langue --- et la modifions judicieusement, alors nous pouvons éliminer les pathologies telles que ci-dessus. O(†$\tilde O$$O$$(\dagger)$

Le résultat est que l'algèbre, lorsqu'elle est convenablement définie, est une relativisation par rapport à un oracle algébrique --- une relativisation algébrique, où chaque oracle obtient une "agitation" --- ce qui signifie est l'ensemble vide dans le diagramme ci-dessus, il en est de même pour .R $\mathrm{R} \setminus \mathrm{A}$$\mathrm{RN}$

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

PS: Une autre formulation pour l'algèbre a été proposée par Impagliazzo, Kabanets et Kolokolova plus tôt, qui place également intérieur , mais n'est pas connue pour être aussi puissante que la notion AW. Voir mon article avec Eric pour une comparaison.$\mathrm{R}$$\mathrm{A}$

Les théorèmes de la hiérarchie temporelle et spatiale se relativisent. Ils sont uniformes, donc ils ne semblent pas se naturaliser.

Je pense que les résultats de diagonalisation indirecte comme les limites inférieures de l'espace temporel de Lance Fortnow, et al. et aussi le résultat de Ryan Williams ne relativise pas car ce ne sont pas des boîtes noires (mais je n'en suis pas sûr). Les preuves ne semblent pas se naturaliser puisqu'elles utilisent des théorèmes de hiérarchie.

Les preuves de permanent non uniforme$TC^0$ utilisent des théorèmes de hiérarchie et ne semblent pas fonctionner pour le cas non uniforme, et ne semblent pas se naturaliser. D'un autre côté, je ne sais pas s'ils relativisent, ils le peuvent avec une notion appropriée de relativisation.

Les preuves interactives ne relativisent pas. Je ne pense pas qu'ils se naturalisent car ils sont uniformes.