Por que a relativização é uma barreira?

Quando eu estava explicando a prova de Baker-Gill-Solovay de que existe um oráculo com o qual podemos ter, , e um oráculo com o qual podemos ter para um amigo, surgiu uma pergunta sobre por que essas técnicas são inadequadas para provar o problema , e não pude dar uma resposta satisfatória.$\mathsf{P} = \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Para colocá-lo de maneira mais concreta, se eu tenho uma abordagem para provar e se consigo construir oráculos para fazer uma situação como a anterior, por que isso invalida o meu método?$\mathsf{P} \neq \mathsf{NP}$

Alguma exposição / pensamentos sobre este tópico?

Para colocá-lo de maneira mais concreta, se eu tenho uma abordagem para provar P and NP e se consigo construir oráculos para fazer uma situação como a anterior, por que isso invalida o meu método?

Observe que o último "se" não é uma condição, porque Baker, Gill e Solovay já construíram esse oráculo. É apenas uma verdade matemática que (1) existe um oráculo em relação ao qual P = NP, e que (2) existe um oráculo em relação ao qual P ≠ NP.

Isso significa que se você tiver uma abordagem para provar P ≠ NP e a mesma prova for igualmente um resultado mais forte "P ^A ≠ NP ^A para todos os oráculos A ", então sua abordagem está fadada ao fracasso, porque isso contradiz (1).

Em outras palavras, há alguma diferença fundamental entre provar P ≠ NP e provar, por exemplo, o teorema da hierarquia do tempo, porque a prova deste último usa apenas diagonalização e é igualmente aplicável a qualquer mundo relativizado.

Obviamente, isso não significa que não há provas para P ≠ NP. Essa prova (se houver) deve falhar em provar o resultado mais forte mencionado acima. Em outras palavras, alguma parte da prova deve distinguir o mundo não relativizante dos mundos relativizados arbitrários.

Já existem boas respostas, mas gostaria de acrescentar alguns pontos.

Suponha que tenhamos uma técnica para resolver problemas, por exemplo, diagonalização . Suponha que queremos mostrar que a técnica não pode resolver um problema específico, por exemplo, vs. . Como pode ser mostrado isso?$\mathsf{P}$$\mathsf{NP}$

Antes de prosseguir, observe que uma técnica como a diagonalização não é um conceito formal aqui (embora possamos fazê-lo). Além disso, o fato de a técnica não poder resolver o problema por si só não significa que não seja útil para resolvê-lo, podemos modificá-lo e / ou combiná-lo com outras técnicas para resolvê-lo.

Agora, voltemos à pergunta. Uma maneira de mostrar que uma técnica não pode resolver um problema específico é mostrar que, se pudesse, também funcionaria em uma estrutura diferente para resolver outra questão, e a resposta que obteríamos nesse caso estaria errada. É o que acontece aqui. Se o diagonalizacao poderia separar a partir de , em seguida, o mesmo argumento pode ser usado para separar a partir de para todos . Mas sabemos que existe um oráculo que é falso (considere qualquer problema como oráculo). Portanto, a diagonalização não pode separar de .$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP^A}$$\mathsf{P^A}$$A$$\mathsf{PSpace}$$\mathsf{NP}$$\mathsf{P}$

O ponto essencial desse argumento é um tipo de princípio de transferência :

podemos transferir um argumento de diagonalização para TMs sem oracle para TMs com oracles.

Isso é possível aqui porque os argumentos de diagonalização são baseados na simulação de máquinas; além disso, a simulação não depende das partes internas das máquinas, mas apenas das respostas finais dessas simulações. Esse tipo de diagonalização é chamado de diagonalização simples . Em uma simulação, não importa como a máquina funcione, importamos apenas a resposta final da máquina. Adicionar um oráculo não mudará isso, portanto a simulação e o argumento também funcionarão na estrutura em que temos oráculos.

Mais formalmente, podemos pensar em um argumento de diagonalização como uma função de uma classe de máquinas (digamos ) para instâncias que mostram que a máquina não pode resolver um problema (digamos ). Essa função de contra-exemplo é a função de diagonalização. Uma diagonalização é simples se os contra-exemplos apresentados não dependerem das partes internas das máquinas, ou seja, se dois DTMs de tempo polinomial tiverem o mesmo idioma, o contra-exemplo mostrando que eles não podem resolver o dado pela função de diagonalização é o mesmo.$\mathsf{P}$$SAT$$SAT$

Você pode se perguntar se isso é uma grande restrição? Por que o contra-exemplo precisaria depender da estrutura interna da máquina? Podemos provar separações usando diagonalização que não podem ser provadas usando diagonalização simples? A resposta é sim. De fato, Kozen mostra em seu artigo de 1978 "Indexação de classes sub-recursivas" (3 anos após o resultado da BGS) que se pode ser separado de então existe um argumento geral de diagonalização para ele. E, na prática, tais argumentos foram encontrados. Por exemplo, os limites inferiores do espaço-tempo de Fortnow e van Melkebeek para o SAT (2000) usam uma técnica chamada diagonalização indireta que fornece uma diagonalização não simples.$\mathsf{NP}$$\mathsf{P}$

Então, a afirmação de que a diagonalização não pode resolver vs. incorreta? Bem, em geral, o que os especialistas entendem por diagonalização aqui é diagonalização simples e há uma boa razão para isso.$\mathsf{P}$$\mathsf{NP}$

Os argumentos gerais de diagonalização são tão gerais que não faz muito sentido chamá-los de técnica, você pode facilmente transformar qualquer argumento de separação em argumento de diagonalização sem muita percepção: se já temos alguma maneira de separar duas classes de complexidade, pode escolher uma função na classe maior e não na menor. Faça qualquer enumeração das máquinas na classe menor. Seja qualquer máquina na enumeração. Temos que definir o contra-exemplo para . Mas já sabemos que não pode resolver o problema, portanto, existe uma instância mostrando isso, defina o valor da função de diagonalização em$M$$M$$M$$M$para ser essa instância. Esta é a visão geral, se você quiser ver os detalhes, consulte o artigo de Kozen.

Verão:

• Quando os especialistas dizem que "a diagonalização não pode resolver vs. ", o que eles querem dizer é " diagonalização simples não pode resolver vs. " e não o geral.$\mathsf{P}$$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$
• A razão pela qual a diagonalização simples não pode separar de é que ela é transferida para a estrutura com oráculos (na literatura é declarada como "diagonalização relativizada") e a separação não se mantém aí.$\mathsf{NP}$$\mathsf{P}$
• A razão pela qual essa transferência da estrutura sem oráculo para a estrutura com oráculos funciona é que a diagonalização simples é baseada na simulação de caixa preta de TMs e não importa como as máquinas funcionam, se ele tem ou não um oráculo.

Dois bons documentos para aprender mais sobre diagonalização são:

• O artigo de pesquisa de Lance Fortnow "Diagonalization", 2001, e
• Artigo de Russell Impagliazzo, Valentine Kabanets e Antonina Kolokolova "Uma abordagem axiomática da algebrização", 2009. (Observe que a algebraização é uma extensão da diagonalização simples .)

Sejam e duas classes de complexidade. Diz-se que uma separação ( ) ou colapso ( ) relativiza se, para todos os oráculos , temos ou respectivamente. A prova de Baker-Gill-Solovay nos diz que ou não relativiza.$\mathrm{A}$$\mathrm{B}$$\mathrm{A} \neq \mathrm{B}$$\mathrm{A} = \mathrm{B}$$\mathrm{O}$$\mathrm{A}^\mathrm{O} \neq \mathrm{B}^\mathrm{O}$$\mathrm{A}^\mathrm{O} = \mathrm{B}^\mathrm{O}$$P = NP$$P \neq NP$

Por que isso é um problema? Quando essa prova foi publicada, a maioria das técnicas e truques que conhecíamos para separar ou colapsar as classes de complexidade foi 'relativizada', na medida em que trabalham com relação a qualquer oráculo. Por exemplo, o teorema da hierarquia temporal (assim como o espaço e as versões não determinísticas dele) 'relativizam': eles provam separações para classes para as quais essa separação relativiza e, de fato, provam o resultado mais forte que a separação mantém em relação a qualquer oráculo.

Se uma técnica ou truque funciona independentemente de haver um oráculo presente, não é possível provar ou pelo argumento acima. Isso significa que um grande número de truques e técnicas que conhecemos não funcionam nesse problema (ou na verdade em muitos problemas abertos). Você também pode usá-lo como uma verificação de integridade para qualquer suposta prova de : verifique se a idéia falha na presença de um oráculo completo com - se ainda funcionar, está errado.$P = NP$$P \neq NP$$P \neq NP$$\mathrm{PSPACE}$