Quais são exemplos naturais de provas não relativizáveis?

Pelo que entendi, uma prova de que P = NP ou P ≠ NP precisaria ser não-relativizável (como nos oráculos da teoria da recursão).

Virtualmente, todas as provas parecem relativizáveis.

Quais são bons exemplos de provas não relativizáveis, do tipo que uma prova P = NP / P ≠ NP precisaria ser, que não seja trivial ou artificial?

(Eu não sou um teórico da recursão, por favor, perdoe a falta de citações.)

[EDIT: melhor publicação do mathoverflow ]

Como observa Steven, o exemplo canônico é . Este colapso não relativizar, no sentido de que existe um oráculo , assunto ao qual . A intuição por que a prova conhecida desse resultado evita a barreira da relativização é que ele usa aritmetização (Yonatan fez alusão a isso em um comentário): um protocolo interativo para o problema completo TQBF é dado considerando uma extensão de um fórmula booleana quantificada para um polinômio de baixo grau sobre um campo adequadamente grande. Se nos for dada uma fórmula booleana relativizada (com oracle gates), essa extensão não existe.$\mathsf{IP} = \mathsf{PSPACE}$$A$$\mathsf{IP}^A \ne \mathsf{PSPACE}^A$$\mathsf{PSPACE}$

Há um refinamento da barreira da relativização - algebrização - devido a Aaronson e Wigderson . Genericamente, a técnica de aritmetização não é suficiente para contornar a barreira da algebrização. Uma inclusão de classe de complexidade algebriza se, para qualquer oráculo e qualquer extensão de para polinômios de baixo grau sobre um campo finito, . Uma separação se torna algebrizada para todos os e todas as extensões ,$\mathsf{C} \subseteq \mathsf{D}$$A$$\tilde{A}$$A$$\mathsf{C}^A \subseteq \mathsf{D}^{\tilde{A}}$$\mathsf{C} \not \subset \mathsf{D}$$A$$\tilde{A}$$\mathsf{C}^{\tilde{A}} \not \subset \mathsf{D}^{A}$. Aaronson e Wigderson mostram que algebriza, mas muitos outros resultados, incluindo , não.$\mathsf{IP} = \mathsf{PSPACE}$$\mathsf{NP} \not \subset \mathsf{P}$

Um exemplo recente de uma técnica que não faz algebrizar ou relativizar é a prova de Ryan Williams de que . A separação não faz algebrize: existe um oráculo e um baixo grau de extensão tal que . Intuitivamente, a razão pela qual a prova evita a barreira é que ela depende da existência de um algoritmo de satisfação mais rápido que o trivial para$\mathsf{NEXP} \not \subset \mathsf{ACC}$$A$$\tilde{A}$$\mathsf{NEXP}^{\tilde{A}} \subset \mathsf{ACC}^A$$\mathsf{ACC}$circuitos, e o algoritmo usa propriedades não relativizantes e não algebrizantes de tais circuitos. Ryan observa no artigo que todos os algoritmos de satisfação mais rápidos que o trivial quebram quando são adicionados oráculos ou extensões algébricas de oráculos.

Há também uma abordagem interessante para entender a relativização através da lógica. Em um manuscrito antigo, Arora, Impagliazzo e Vazirani definem um sistema de axiomas de modo que os resultados da relativização sejam exatamente aqueles que se seguem dos axiomas, enquanto os resultados não relativizantes são independentes do sistema. Um artigo de Impagliazzo, Kabanets e Kolokolova faz algo semelhante para a algebrização, introduzindo um axioma adicional aos definidos por Arora, Impagliazzo e Vazirani. Eles mostram que os resultados não relativizadores mais conhecidos seguem seus axiomas, enquanto P vs NP, entre outros, é independente deles.

Desculpas se eu entendi algo errado, eu não sou um especialista.

Aqui está uma lista de provas não relativizáveis:

1. Teorema do PCP

2. O comprometimento dependente da instância implica um protocolo de conhecimento zero:
   uma equivalência entre zero conhecimento e compromissos

3. Não há ofuscador de circuito eficiente para "caixa preta virtual" para circuitos gerais:
   uma equivalência entre zero conhecimento e compromissos

4. O PSPACE é redutível à avaliação de um produto sucinto do : o PSPACe sobrevive a gargalos de três bits$S_5$
   

5. Contra provadores não enredados, a NEXP possui sistemas de prova com dois provadores minimamente interativos: Sistemas de prova com um e
   dois provadores: seu poder e seus problemas

6. Contra provadores possivelmente entrelaçados, o NEXP possui protocolos MIP mais interativos:
   Uma prova interativa de vários provadores para o som NEXP contra provadores entrelaçados

7. A NP possui provas de conhecimento NISZK de provadores eficientes com extração perfeita de conhecimento em um modelo de bits ocultos de "distribuição não padronizada e com amostragem eficiente" e provas de conhecimento NIPZK de provadores eficientes no modelo de bits ocultos (reais). Além disso, se o amostrador tiver uma pequena probabilidade de gerar (e a solidez for necessária apenas quando o amostrador não produzir ), o "NISZK" da frase anterior poderá ser substituído por "NIPZK" . Jonathan Katz, Tópicos avançados em criptografia, Palestra 13$\perp$$\perp$
   
   Nota: A extração de conhecimento perfeita é seguida pela inspeção da parte da solidez na página 2. A extração de conhecimento (não perfeita) é mantida pelo mesmo motivo que a solidez não perfeita, conforme descrito na parte superior da página 5. O conhecimento zero perfeito pode ser obtido com o simulador usando a matriz hamiltoniana como sua permutação , e algumas das cadeias de bits reais correspondentes aos bits tendenciosos com valor 0 como elas próprias, principalmente em locais diferentes. A sentença "além disso" segue com a saída do amostrador$C_i$$\pi$$\perp$ se não fosse possível escolher um elemento de {0,1,2,3, ..., n! -1} perfeitamente uniformemente em um período de tempo suficientemente pequeno, pois essa escolha permitiria a geração perfeitamente uniforme de um elemento matriz de gráfico de ciclo direcionado ou permutação dos vértices.

Esta é uma boa pesquisa de campo por um especialista líder que resume / detalha alguns dos pontos das outras respostas até agora e tem exemplos adicionais.

[1] O papel da relativização na teoria da complexidade Fortnow

Vários resultados recentes não-relativizantes na área de provas interativas fizeram com que muitas pessoas revisassem a importância da relativização. Neste artigo, veremos como os teóricos da complexidade usam e usam incorretamente os resultados do Oracle. Prestamos atenção especial aos novos sistemas interativos de provas e resultados de verificação de programas e tentamos entender por que eles não se relativizam. Damos novos resultados que podem nos ajudar a entender melhor essas perguntas.