Existem técnicas canônicas de não relativização?

28

Em muitos domínios, existem técnicas canônicas que todo mundo que trabalha no campo deve dominar. Por exemplo, para reduções do espaço de log, o "truque de bit" para composição que consiste em não construir a saída completa da função composta, mas sempre pedindo para recalcular o resultado para cada bit de saída, permitindo manter as restrições do espaço de log.

Minha pergunta é sobre técnicas não relativizantes. Os teóricos descreveram algumas operações não relativizantes fundamentais, ou existe um truque diferente para cada prova não relativizante conhecida?

Ludovic Patey
fonte
talvez um conceito central para relativização (não) é "algoritmos de compressão"
vzn
o que é um dispositivo abstrato de acordo com Automata

Respostas:

40

Na verdade, existe apenas uma técnica "não-relativizante" emblemática: aritmetização (a técnica usada nas provas de IP = PSPACE, MIP = NEXP, PP⊄SIZE (n k ), MA EXP ⊄P / poly e vários outros resultados )

Entretanto, a prova de que todas as linguagens NP têm provas computacionais de zero conhecimento (supondo que existam funções unidirecionais), devido a Goldreich, Micali e Wigderson, usaram uma técnica não relativizante diferente (ou seja, as simetrias do problema 3-COLORING )

Arora, Impagliazzo e Vazirani argumentaram que mesmo a "verificação local", a propriedade dos problemas completos de NP usados ​​na prova do Teorema de Cook-Levin original (assim como o Teorema de PCP), deveria contar como uma técnica não relativizante ( embora Lance Fortnow tenha escrito um artigo argumentando o contrário). O ponto de discórdia é se faz sentido relativizar a classe de complexidade de "problemas verificáveis ​​localmente".

Os argumentos pebbling usados ​​nos resultados da década de 1970, como TIME (n) - NTIME (n), foram apresentados como outro exemplo de uma técnica não relativizante.

Para mais, você pode conferir meu trabalho de algebrização com Wigderson , e especialmente as referências nele. Tivemos que praticamente catalogar as técnicas não relativizantes existentes para descobrir quais eram e não eram abrangidas pela barreira da algebrização.

Adendo: Acabei de perceber que esqueci de mencionar a computação quântica baseada em medição (MBQC) , que foi recentemente usada com grande efeito por Broadbent, Fitzsimons e Kashefi para obter teoremas de complexidade quântica (como QMIP = MIP * e BQP = MIP provadores de BQP emaranhados e verificador de BPP) que provavelmente não conseguem relativizar.

Scott Aaronson
fonte