Pruebas, Barreras y P vs NP

Es bien sabido que cualquier prueba que resuelva la cuestión P vs NP debe superar la relativización , las pruebas naturales y las barreras de algebrización . El siguiente diagrama divide el "espacio de prueba" en diferentes regiones. Por ejemplo, $RN$ corresponde al conjunto de pruebas que se relativizan y naturalizan. $GCT$ (teoría de la complejidad geométrica) es, por supuesto, la región estrictamente exterior.

Nombre algunas pruebas junto con las regiones más conocidas a las que pertenecen. Colocarlos en una mejor manera posible, es decir, si una prueba es conocida a relativizar, naturalizar y algebrize entonces debe ser colocado en $RNA$ no sólo en $RN$ . Si una prueba se relativiza pero no se naturaliza, pertenece a $R$ ${\setminus}$ $N$ y así sucesivamente.

Creo que necesita volver a dibujar su diagrama de Venn ... cualquier contención de clases de complejidad que se relativice también se algebrizará, al menos en el sentido de Aaronson y Wigderson. Es decir, el acceso a la "extensión de bajo grado" de un oráculo es solo más poderoso que el acceso al oráculo. De manera similar, cualquier oráculo que muestre que una separación requiere técnicas "no algebrizantes" implica que también se requieren técnicas "no relativizantes".

Contrariamente a algunas afirmaciones anteriores en este hilo, no se sabe que la algebrización en el sentido de Aaronson & Wigderson subsuma la relativización. Por ejemplo,

Es una declaración que relativiza. (De hecho, tiene una prueba relativizante, lo que sea que eso signifique para el lector). Pero no se sabe que algebriza, como lo aludieron Aaronson y Wigderson en la Sección 10.1 de su artículo [1]. (En consecuencia, mientras AW nos dice que en el diagrama anterior debe estar fuera de , es concebible que encuentra dentro!)$\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}$

Sin embargo, un trabajo reciente de Eric Bach y yo [2] ofrece una formulación de algebrización que subsume la relativización. Básicamente, si tomamos la noción AW de un oráculo algebraico --- denotado como para algún lenguaje --- y lo modificamos sabiamente, entonces podemos eliminar las patologías como arriba.$\tilde O$$O$$(\dagger)$

El resultado es que la algebrización, cuando se define adecuadamente, es relativización con respecto a un oráculo algebraico --- una relativización algebraica, donde cada oráculo obtiene un "meneo" --- que significa es el conjunto vacío en el diagrama anterior, por lo tanto, también lo es .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/

PD: Impagliazzo, Kabanets y Kolokolova propusieron otra formulación para la algebrización, que también coloca dentro de , pero no se sabe que sea tan poderosa como la noción AW. Vea mi artículo con Eric para una comparación.$\mathrm{R}$$\mathrm{A}$

Los teoremas de la jerarquía del tiempo y el espacio se relativizan. Son uniformes, por lo que no parecen naturalizarse.

Creo que la diagonalización indirecta resulta como los límites inferiores de TimeSpace de Lance Fortnow, et al. y también el resultado de Ryan Williams no se relativiza porque no son caja negra (pero no estoy seguro de esto). Las pruebas no parecen naturalizarse ya que usan teoremas de jerarquía.

Las pruebas de permanente no uniforme$TC^0$ usan teoremas de jerarquía y no parecen funcionar para casos no uniformes, y no parecen naturalizarse. Por otro lado, no sé si se relativizan, pueden hacerlo con una noción adecuada de relativización.

Las pruebas interactivas no se relativizan. No creo que se naturalicen ya que son uniformes.