Por que as provas de não relativização são preferidas às de relativização?

Peço desculpas, mas mesmo após essas duas outras postagens: aqui e aqui ainda estou tendo problemas para entender as TMs e a relativização do oracle. Esta questão vem à questão de um ângulo diferente:

Por que as provas não relativizantes são consideradas mais válidas do que argumentos baseados em resultados relativizados?

Por exemplo, temos uma prova não relativizante de IP = PSPACE, mas não poderíamos dizer um argumento contrário pelo fato de existir um oráculo que os separa (percebo a partir de uma resposta a uma pergunta que anteriormente perguntei que esse oráculo existe devido a uma diferença estrutural entre as duas classes de complexidade, mas vejo isso como uma evidência ainda maior de que as classes são diferentes em aspectos importantes e podem não ser iguais).

Por outro lado, por que concluímos do fato de que existem oráculos e tal forma que e que serão necessárias técnicas de não relativização para resolver P vs. NP e não apenas resolver que os oráculos levam a contradições inerentes, pois não podemos ter P = NP e P$A$$B$$P^A = NP^A$$P^B \neq NP^B$$\neq$NP? Novamente, percebo em um post anterior que podemos ver as TMs da Oracle como diferentes modelos de computação que podem resolver problemas que as TMs comuns não podem, mas vejo isso como semelhante à "tática da teoria dos tipos" usada no Principia Mathematica que, de acordo com minha Godel (através dos teoremas da incompletude) mostrou-se insuficiente para resolver problemas de completude e consistência de sistemas axiomáticos.

Deixe-me tentar responder à sua pergunta multifacetada usando uma analogia da teoria dos números (ou melhor, aritmética Peano). O ponto de vista platônico sustenta que toda pergunta sobre números naturais tem uma resposta SIM / NÃO. Isso é conhecido como "aritmética verdadeira". No entanto, como Gödel mostrou, algumas proposições relativas a números naturais não podem ser provadas nem refutadas. O ponto de vista platonista ainda sustenta que essas proposições têm um valor de verdade definido em relação ao conjunto "verdadeiro" de números naturais; Gödel apenas mostrou que a lista não finita de axiomas ¹ pode especificar o verdadeiro conjunto de números naturais.

Vamos ver o que isso implica em relação à questão P vs. NP. O ponto de vista platônico sustenta que P = NP ou P$\neq$NP. Pode ser que P vs. NP seja independente dos fundamentos da matemática (por exemplo, ZFC); nesse caso, seremos capazes de provar nem P = NP nem P$\neq$NP. Mas, segundo a maioria dos pesquisadores, essa possibilidade é improvável. Portanto, gostaríamos realmente de saber se P = NP ou não no mundo real , que é o mesmo que ² se P = NP ou não, de acordo com os fundamentos padrão da matemática . Esta é a questão de pesquisa.

E os modelos relativizados? Deixe-me oferecer outra analogia da teoria dos números. Se uma identidade polinomial é verdadeira sobre os números inteiros, também é verdadeiro módulo$p$ para cada prime $p$. Portanto, para refutar uma identidade, basta mostrar que ela não se sustenta por$p$. Podemos pensar no módulo inteiro$p$como um "modelo relativizado". Vamos considerar um exemplo:$1 + 1 = 0$ módulo $2$ mas não módulo $3$. Isso significa que não temos mais certeza se$1 + 1 = 0$ou não? De modo nenhum. Nós sabemos isso$1 + 1 = 2$, e em particular $1 + 1 \neq 0$. Mas em alguns modelos relativizados, essa equação falha.

O princípio local-global (informal) afirma que, em algumas situações, existe um conjunto de "modelos relativizados" que é completo para algumas afirmações da teoria dos números. O exemplo clássico é de formas quadráticas: dada uma forma quadrática$Q$ e um número $n$, então $Q$ representa $n$ sobre os racionais (ou seja, $n$ está na imagem de $Q$ quando as entradas são números racionais arbitrários) se representa $n$ sobre os números reais e os $p$-adics.

Infelizmente, não temos teoremas semelhantes para a teoria da complexidade. Em particular, dado o valor verdadeiro das afirmações relativizadas, não podemos deduzir nada sobre a afirmação original. A situação é ainda pior: não é mais o caso de um resultado verdadeiro no mundo "verdadeiro" também ser relativizado para qualquer oráculo. Portanto, não podemos nem esperar declarações como o princípio local-global aqui.

Algo como "técnicas relativizadas" também ocorre na aritmética Peano. Há declarações sobre os números naturais que podem ser provados no ZFC, mas não na aritmética do Peano. Os exemplos clássicos são o teorema de Paris-Harrington e o teorema de Goodstein. Todas as provas na aritmética Peano estão "relativizando" no sentido em que são válidas em todos os modelos da aritmética Peano. Os teoremas de Paris-Harrington e Goodstein falham em alguns modelos não-padrão da aritmética Peano, mas estes não representam a aritmética verdadeira; na aritmética verdadeira, os teoremas são válidos. O problema está na aritmética do Peano, e não nas próprias declarações: existem algumas propriedades dos números naturais que ele não descreve, permitindo que esses modelos fora do padrão entrem. Gödel mostrou que esse problema ocorre em todos os modelos de primeira ordem de aritmética.

Agora podemos responder às suas perguntas:

1. Por que uma prova não relativizante de IP = PSPACE é preferível às separações oracle das mesmas duas classes? Nós nos preocupamos apenas com a questão IP = PSPACE? no mundo "verdadeiro". Não importa o que acontece nos mundos relativizados. Como existem oráculos que separam IP e PSPACE, as provas de IP = PSPACE devem ser não relativizantes. A situação é análoga à que envolve os teoremas de Paris – Harrington e Goodstein.

   Um problema diferente é que talvez não esteja claro como definir as versões relativizadas dessas classes. Isso impede a apresentação de resultados relativizados, mesmo como evidência.

2. P = NP vale com relação a algum oráculo e falha com relação a outro; por que concluímos que são necessárias técnicas não relativizadoras, e não que oráculos levam a contradições inerentes? É o mesmo que a situação de$1+1 \neq 0$acima. Esse teorema é verdadeiro, mas possui diferentes valores de verdade em diferentes "mundos relativizados" correspondentes ao módulo de números inteiros$p$ para diferentes valores de $p$. Isso significa que uma prova de$1+1 \neq 0$ deve incluir algum passo que não contenha todo o módulo $p$. Isso não significa que o módulo de trabalho$p$ "leva a contradições inerentes".

3. Não estamos vendo algo semelhante na "teoria dos tipos" desenvolvida no Principia Mathematica? A teoria dos tipos foi desenvolvida como uma base consistente para a matemática, depois que Russell descobriu que a teoria dos conjuntos ingênua é inconsistente (usando seu paradoxo). Nenhuma dessas dificuldades fundamentais foi encontrada na teoria da complexidade.

4. Quais são as implicações do teorema da incompletude de Gödel? O teorema da incompletude levanta a possibilidade de que P vs. NP seja independente dos fundamentos atuais da matemática. Mas isso é considerado improvável pela maioria dos pesquisadores. Muitos teoremas difíceis foram provados no passado; alguns deles estavam abertos há séculos (por exemplo, o último teorema de Fermat). O fato de um teorema ser difícil não é motivo para pensar que está além da solução.

Isso deixa uma pergunta que você não fez: por que nos preocupamos com resultados relativizados? Eu não sei o motivo histórico. Pode ser que essas técnicas sejam comuns em áreas relacionadas que serviram como fontes de inspiração. No início, as pessoas podem ter esperado que os resultados relativizado não implicam resultados absolutos. Um bom exemplo é a hipótese do oráculo aleatório, que afirma que, se uma afirmação da teoria da complexidade se aplica a um oráculo aleatório, ela se aplica absolutamente. Por exemplo, embora P vs. NP seja "indeciso" em relação a um oráculo arbitrário, Baker, Gill e Solovay mostraram que P$\neq$NP em relação a um oráculo aleatório. Isso implica que P$\neq$NP? O fato de IP = PSPACE refutar essa hipótese. Desde esse ponto, muito menos atenção foi dada aos resultados do oráculo, e eles agora são bastante fora de moda. Eles se tornaram um objeto de estudo por si só, mas sem pretensões de serem relevantes para separar P de NP.

Notas finais:

1. A axiomatização usual da aritmética Peano, na verdade, usa um número finito de esquemas de axiomas . O resultado de Gödel é ainda mais generalizado, como Andrej Bauer indica em seus comentários ponderados.

2. Veja os comentários de Andrej Bauer para uma opinião divergente.