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

13

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 ]

Sai
fonte
6
Para copiar minha sugestão do MO e evitá-la: o exemplo canônico de que conheço é a prova de IP = PSPACE, onde particularmente a inclusão do PSPACE no IP é feita, mostrando uma prova interativa para um PSPACE específico problema completo, uma técnica não-relativizável - problemas particulares não são relativizados.
Steven Stadnicki
5
@AndrejBauer AFAIK, não, porque não existe algo como 'TQBF relativizado' - na verdade, existem oráculos com , então a prova não pode relativizar canonicamente . AIPAPSPACEA
Steven Stadnicki
4
@Steven: O TBQF relativizado pode ser formado ao permitir portas oracle, em vez de apenas portas lógicas (padrão).
3
@RickyDemer Mesmo assim, o cerne da prova funciona ao interpretar a fórmula como um polinômio de baixo grau, que não ocorre quando você tem (digamos) um oráculo uniformemente aleatório.
Yonatan N
1
O resultado de P =? NP na relativização é conhecido como o teorema de Baker-Gill-Solovay, 1975 . a prova também pode ser encontrada, por exemplo, em Hopcroft / Ullman . @ richerby / Sai, não há razão para migrar após as duas perguntas já terem sido inseridas, é mais para referência futura. Observe também que parece não haver nenhuma política oficial de cross-exchange para troca cruzada (portanto, é possível entender alguma confusão).
vzn

Respostas:

24

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.IP=PSPACEAIPAPSPACEAPSPACE

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 ,CDAA~ACADA~CDAA~CA~DA. Aaronson e Wigderson mostram que algebriza, mas muitos outros resultados, incluindo , não.IP=PSPACENPP

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 paraNEXPACCAA~NEXPA~ACCAACCcircuitos, 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.

Sasho Nikolov
fonte
7
Existem outros exemplos de provas não relativizantes no artigo de Aaronson-Wigderson, como , , etc.NEXPMIPMAEXPP/polyPromiseMASIZE(nk)
6266 Robin Kothari
10

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 bitsS5

  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

    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 amostradorCiπ 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.

Kaveh
fonte
7

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.

vzn
fonte
6
+1 Esta é uma boa pesquisa, mas deve-se mencionar que pesquisa o estado do mundo até 1993 #
Sasho Nikolov
verdadeiro; seria útil que os autores incluíssem datas em seus artigos mais ... uma pesquisa mais recente também seria útil, o tópico parece raramente pesquisado. essa área parece não mudar tanto e não está claro quantos novos resultados surgiram desde essa data.
vzn
3
para novos resultados: Eu acho que alguns novos resultados do oracle apareceram desde que se relacionam com classes de complexidade quântica. mais importante, houve desenvolvimentos em termos do significado dos resultados do oráculo: a barreira da algebrização e a prova não-algebrizante de Ryan da minha resposta, um artigo relacionado cs.sfu.ca/~kabanets/papers/act-full.pdf e possivelmente O trabalho de Boaz Barak em reduções que não são de caixa preta em criptografia.
Sasho Nikolov