Provas, Barreiras e P vs NP

É sabido que qualquer prova que resolva a questão P vs NP deve superar a relativização , provas naturais e barreiras à algebrização . O diagrama a seguir divide o "espaço de prova" em diferentes regiões. Por exemplo, corresponde ao conjunto de provas que relativizam e naturalizam. (Teoria da Complexidade Geométrica) é obviamente a região estritamente externa.G C $RN$$GCT$

Cite algumas provas junto com as regiões mais conhecidas às quais elas pertencem. Coloque-os da melhor maneira possível, ou seja, se for sabido que uma prova relativiza, naturaliza e algebriza, ela deve ser colocada no não apenas no . Se uma prova é relativizada, mas não naturalizada, ela pertence a e assim por diante.R N R ∖$RNA$$RN$$R$ ${\setminus}$ $N$

Eu acho que você precisa redesenhar seu diagrama de Venn ... qualquer restrição de classes de complexidade que relativize também será alterada, pelo menos no sentido de Aaronson e Wigderson. Ou seja, o acesso à "extensão de baixo grau" de um oráculo é apenas mais poderoso que o acesso ao oráculo. Da mesma forma, qualquer oráculo que mostre que uma separação requer técnicas "não-algebrizantes" implica que também sejam necessárias técnicas "não-relativizantes".

Ao contrário de algumas alegações anteriores neste tópico, a algebrização no sentido de Aaronson & Wigderson não é conhecida por incluir a relativização. Por exemplo,

é uma afirmação que relativiza. (De fato, há uma prova relativizante, o que quer que isso possa significar para o leitor.) Mas não se sabe que algebrize, como aludido pelos próprios Aaronson & Wigderson na Seção 10.1 de seu artigo [1]. (Consequentemente, enquanto o AW nos diz que no diagrama acima, deve estar fora de , é possível que está 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}$

No entanto, um trabalho recente de Eric Bach e eu [2] fornece uma formulação de algebrização que inclui a relativização. Basicamente, se pegarmos a noção AW de um oráculo algébrico - denotado como para alguma linguagem --- e modificá-lo sabiamente, podemos eliminar as patologias como acima.$\tilde O$$O$$(\dagger)$

O resultado é que a algebrização, quando definida adequadamente, é a relativização em relação a um oráculo algébrico - uma relativização algébrica, onde todo oráculo recebe um "movimento" - --- o que significa é o conjunto vazio no diagrama acima, portanto .$\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: Outra proposta de algebrização foi proposta por Impagliazzo, Kabanets e Kolokolova anteriormente, que também coloca dentro de , mas não é conhecido por ser tão poderoso quanto a noção de AW. Veja meu artigo com Eric para uma comparação.$\mathrm{R}$$\mathrm{A}$

Os teoremas da hierarquia do tempo e do espaço se relativizam. Eles são uniformes, por isso não parecem naturalizar.

Penso que resultados de diagonalização indireta, como os limites inferiores do TimeSpace de Lance Fortnow, et al. e também o resultado de Ryan Williams não relativiza porque não é caixa preta (mas não tenho certeza disso). As provas não parecem naturalizar, pois usam teoremas de hierarquia.

As provas de permanente não uniforme em$TC^0$ usam teoremas de hierarquia e não parecem funcionar para casos não uniformes, e não parecem naturalizar. Por outro lado, não sei se eles se relativizam, podem com uma noção adequada de relativização.

As provas interativas não são relativizadas. Não acho que eles naturalizem porque são uniformes.