Complexidade de prova de uma prova ou reprovação de P = NP

15

Houve alguma pesquisa sobre a complexidade da prova de uma resolução para o problema P = NP? Caso contrário, dada a falta de progresso no problema, não seria razoável conjeturar que qualquer prova que resolva o problema P = NP exigirá um número super-polinomial de etapas?

Tony Johnson
fonte
18
Talvez eu não esteja entendendo sua pergunta, mas qualquer resolução para P vs NP seria uma prova de tamanho constante, sim?
Kurt Mueller #
@Kurt Muller. A prova exigirá um número super-polinomial de etapas, com base no número de símbolos necessários para codificar o problema P = NP.
Tony Johnson
11
@TonyJohnson O superpolinômio em uma constante ainda é uma constante.
David Richerby

Respostas:

14

Sabe-se que qualquer prova de limites inferiores do circuito super-polinomial (que são afirmações um pouco mais fortes que PNP ) requer provas de tamanho super-polinomial e até mesmo exponenciais em sistemas de prova fracos, como resolução. Generalizar isso para sistemas de prova mais fortes é um problema em aberto bem conhecido.

Veja a seção 5 desta pesquisa de A. Razborov, onde essas coisas são mostradas.

Jan Johannsen
fonte
24

A complexidade da prova só faz sentido quando há uma sequência de instruções, dependendo do parâmetro . Por exemplo, a proposição P H P n afirma (informalmente) que não há bijeção [ n + 1 ] [ n ]nPHPn[n+1][n] . Essa sequência de proposições é difícil para certos sistemas de provas proposicionais.

A declaração é uma declaração única, portanto você não pode aplicar diretamente a complexidade da prova. No entanto, a seguinte sequência de instruções faz sentido, para funções específicas s ( n ) : "não há circuito de tamanho s ( n ) resolvendo corretamente o SAT para instâncias de comprimento n ". Isso foi considerado na literatura, por exemplo, por Razborov (que considerou a configuração da complexidade uniforme da prova, ou seja, aritmética limitada).PNPs(n)s(n)n

Yuval Filmus
fonte
5

Temos 3 casos:

  • Não existe uma prova de que a . Então existe um algoritmo que resolve o problema "Emita uma prova de que P = N P " é executado no tempo O ( 1 ) . Ele codifica a prova na própria máquina de Turing e a emite. É executado ao mesmo tempo, independentemente da sua entrada.P=NPP=NPO(1)

  • Da mesma forma, se existe uma prova de que , então podemos escrever um algoritmo emitindo essa prova em O ( 1 ) .PNPO(1)

  • Se não houver prova de ambos os casos, a complexidade mínima para encontrar uma prova é O()

Só porque não encontramos nenhuma prova, não significa que ela não exista, e as classes de complexidade são definidas em termos do que existe.

Mais precisamente, não podemos saber exatamente quão difícil é encontrar uma prova de P=NP

O que sabemos é que, em geral, o problema de "Pegue uma declaração na lógica do predicado e determine se há uma prova disso" é indecidível. Portanto, não há procedimentos genéricos de geração de provas nos quais possamos conectar P vs NP, que garantam um resultado.

jmite
fonte
-2

Se P = NP, tudo o que você precisa fazer é criar um algoritmo de tempo polinomial para resolver um problema completo de NP e provar que ele é realmente polinomial (o que pode ser difícil, por exemplo, o algoritmo Simplex geralmente roda muito rápido, mas provando que corre rápido parece incrivelmente difícil).

n100

gnasher729
fonte
P=?NP? "
David Richerby 29/11/16
Há também o resultado (improvável, mas inteiramente possível) de que P = NP, mas não existe um algoritmo de tempo polinomial comprovadamente uniforme para, por exemplo, o SAT.
Steven Stadnicki 29/11