Implicações da improvabilidade de

Eu estava lendo " O P Versus NP é formalmente independente? ", Mas fiquei intrigado.

É amplamente aceito na teoria da complexidade que . Minha pergunta é sobre o que se não for possível (digamos no ). (Vamos supor que descobrimos apenas que é independente do mas não há mais informações sobre como isso é comprovado.)$\mathsf{P} \neq \mathsf{NP}$$ZFC$$\mathsf{P} \neq \mathsf{NP}$$ZFC$

Quais serão as implicações desta declaração? Mais especificamente,

dureza

Supondo que capture os algoritmos eficientes ( tese de Cobham – Edmonds ) e , provamos que os resultados de implicam que eles são além do alcance atual de nossos algoritmos eficientes. Se provarmos a separação, significa que não há algoritmo de tempo polinomial. Mas o que significa um resultado se a separação não é possível? O que acontecerá com esses resultados?$\mathsf{P}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{NP\text{-}hardness }$$\mathsf{NP\text{-}hardness}$$\mathsf{NP\text{-}hardness }$

algoritmos eficientes

A improvabilidade da separação significa que precisamos alterar nossa definição de algoritmos eficientes?

Sua pergunta pode ser melhor formulada: "Como a teoria da complexidade seria afetada pela descoberta de uma prova de que P = NP é formalmente independente de algum sistema axiomático forte?"

É um pouco difícil responder a essa pergunta em abstrato, ou seja, na ausência de ver os detalhes da prova. Como Aaronson menciona em seu artigo, provar a independência de P = NP exigiria idéias radicalmente novas, não apenas sobre a teoria da complexidade, mas sobre como provar as declarações de independência. Como podemos prever as consequências de um avanço radical cuja forma não podemos adivinhar atualmente?

Ainda assim, existem algumas observações que podemos fazer. Após a prova da independência da hipótese do continuum da ZFC (e mais tarde da ZFC + cardeais grandes), um número considerável de pessoas chegou ao ponto de vista de que a hipótese do continuum não é verdadeira nem falsa . Poderíamos perguntar se as pessoas chegarão à conclusão de que P = NP "não é verdadeiro nem falso" na sequência de uma prova de independência (por uma questão de argumento, suponhamos que P = NP seja independente do ZFC + qualquer grande axioma cardinal). Meu palpite não é. Aaronson basicamente diz que não faria. O segundo teorema da incompletude de Goedel não levou ninguém que eu conheça a argumentar que "o ZFC é consistente" não é verdadeiro nem falso.e a maioria das pessoas tem fortes intuições de que declarações aritméticas - ou pelo menos declarações aritméticas simples como "P = NP" - devem ser verdadeiras ou falsas. Uma prova de independência seria apenas interpretada como dizendo que não temos como determinar qual de P = NP e P NP é o caso.$\ne$

Pode-se também perguntar se as pessoas interpretariam esse estado de coisas como dizendo que há algo "errado" em nossas definições de P e NP. Talvez devêssemos refazer os fundamentos da teoria da complexidade com novas definições mais fáceis de trabalhar? Neste ponto, acho que estamos no reino da especulação selvagem e infrutífera, onde estamos tentando atravessar pontes que não chegamos e tentando consertar coisas que ainda não estão quebradas. Além disso, nem está claro que algo poderiaser "quebrado" neste cenário. Os teóricos dos conjuntos são perfeitamente felizes assumindo quaisquer axiomas cardinais grandes que considerem convenientes. Da mesma forma, os teóricos da complexidade também podem, neste mundo hipotético do futuro, ser perfeitamente feliz assumindo quaisquer axiomas de separação que eles acreditam serem verdadeiros, mesmo que sejam comprovadamente prováveis.

Em resumo, nada de muito se segue logicamente de uma prova de independência de P = NP. A face da teoria da complexidade pode mudar radicalmente à luz de uma inovação tão fantástica, mas teremos que esperar e ver como é a inovação.

Esta é uma pergunta válida, apesar de talvez um pouco infelizmente formulada. A melhor resposta que posso dar é esta referência:

Scott Aaronson: P versus NP é formalmente independente . Boletim da Associação Europeia de Ciência da Computação Teórica, 2003, vol. 81, páginas 109-136.

Resumo: Esta é uma pesquisa sobre a questão do título, escrita para pessoas que (como o autor) veem a lógica como proibitiva, esotérica e distante de suas preocupações habituais. Começando com um curso intensivo sobre a teoria dos conjuntos de Zermelo Fraenkel, ele discute a independência do oráculo; provas naturais; resultados de independência de Razborov, Raz, DeMillo-Lipton, Sazanov e outros; e obstáculos para provar P vs. NP independentemente de fortes teorias lógicas. Termina com algumas reflexões filosóficas sobre quando se deve esperar que uma pergunta matemática tenha uma resposta definitiva.

$[ZFC][1]$. Significa simplesmente que a teoria não pode provar nem a afirmação nem sua negação. Isso não significa que a afirmação não tem um valor de verdade, não significa que não podemos saber o valor de verdade da afirmação; poderemos adicionar novos axiomas razoáveis ​​que tornarão a teoria forte o suficiente para poder para provar as declarações ou sua negação. No final, a provabilidade em uma teoria é um conceito abstrato formal. Está relacionado à nossa experiência no mundo real apenas como modelo.

$\mathsf{P}$

$\Sigma_1$$\Pi_1$Topologia via lógica ", 1996.)

$\mathsf{P} \neq \mathsf{NP}$$\Sigma_2$e pesquise as postagens na lista de correio do FOM .

Conforme comprovado neste artigo:

http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0699.revised.pdf

Se P! = NP puder ser independente da Aritmética Peano, NP terá limites superiores no tempo determinístico extremamente próximo do polinômio. Em particular, nesse caso, existe um algoritmo DTIME (n ^ 1og * (n)) que calcula o SAT corretamente em infinitos intervalos enormes de comprimentos de entrada.

Apenas alguns pensamentos desmedidos sobre isso. Sinta-se livre para criticar.

Seja Q = [não pode provar (P = NP) e não pode provar (P / = NP)]. Suponha Q para uma contradição. Também assumirei que todas as descobertas conhecidas sobre P vs NP ainda são viáveis. Em particular, todos os problemas de NP são equivalentes no sentido de que, se você puder resolver um deles em tempo polinomial, poderá resolver todos os outros em tempo polinomial. Então, seja W um problema completo de NP; W representa igualmente todos os problemas no NP. Por causa de Q, não é possível obter um algotitmo A para resolver W em tempo polinomial. Caso contrário, temos prova de que P = NP, o que contradiz Q (1) (*). Observe que todos os algoritmos são computáveis ​​por definição. Dizer que A não pode existir implica que não há como calcular W em tempo polinomial. Mas isso contradiz Q (2). Nos resta rejeitar (1) ou rejeitar (2). Qualquer um dos casos leva a uma condenação. Assim, Q é uma contradição,

(*) Você pode dizer: "Aha! A pode existir, mas simplesmente não conseguimos encontrá-lo". Bem, se A existia, podemos enumerar todos os programas para encontrar A enumerando de programas menores para programas maiores, começando com o programa vazio. A deve ser finito porque é um algoritmo; portanto, se existe, o programa de enumeração para encontrá-lo deve terminar.