Sobre a possibilidade de P versus NP

11

Primeiro, meu entendimento do teorema da incompletude de Gödel (e da lógica formal em geral) é muito ingênuo, e também meu conhecimento sobre ciência da computação teórica (ou seja, apenas um curso de graduação realizado enquanto ainda estou na graduação), então essa pergunta pode ser muito ingênuo.

Tanto quanto pude encontrar, a possibilidade de P versus NP é um problema em aberto.

Agora:

  • O primeiro teorema da incompletude de Gödel afirma que pode haver afirmações verdadeiras, mas não prováveis ​​nem desaprováveis.
  • Se uma solução polinomial for encontrada para um problema NP-completo, isso prova que P = NP.

Portanto, suponha que P = NP não seja comprovável:
Isso significa que nenhum exemplo de solução polinomial para um problema completo de NP pode ser encontrado (caso contrário, isso seria uma prova).
Porém, se nenhum exemplo de solução polinomial para um problema completo de NP puder ser encontrado, isso significa que P = NP é falso (provando isso, o que significa que a afirmação é comprovável), o que leva a uma contradição; portanto, P = NP deve ser comprovado .

Isso parece uma prova da possibilidade de P = NP para mim, mas acho que é extremamente provável que seja devido à minha falta de compreensão dos tópicos lógicos envolvidos. Alguém poderia me ajudar a entender o que há de errado nisso?

Alvaro
fonte
3
Parece-me que você tem uma confusão mais básica sobre como algo pode ser verdade, mas não pode ser provado. Verifique o tour e o centro de ajuda para obter o escopo deste site. Eu acho que isso é mais adequado para Ciência da Computação ou Matemática .
Kaveh
este semifamous papel provas naturais por Razborov / Rudich é aplicável a esta pergunta
vzn
Você pode também estar interessado em monografia Hartmanis' 'Cálculos viável e Provable Propriedades Complexidade', que aborda essencialmente o que acontece se considerarmos apenas os problemas que estão comprovadamente em P, comprovadamente em NP, etc.
Joshua Grochow

Respostas:

21

Se P = NP, deve haver algoritmos de tempo polinomial para problemas completos de NP. No entanto, pode não haver nenhum algoritmo que resolva um problema NP completo e que seja executado em tempo polinomial.

David Richerby
fonte
1
Então, o que você está dizendo é que a falha é que pode haver um exemplo de solução polinomial, mas você pode não ser capaz de provar que é polinomial? Porque então não é considerado na prova pelo exemplo, então ainda não vejo a falha.
Alvaro
3
Suponha que P = NP, mas isso não é comprovável. Isso significa que existe um algoritmo de tempo polinomial A para 3-SAT. Se você pudesse provar que A era um algoritmo poli-tempo para 3-SAT, isso contradiz a improvabilidade de P = NP. Portanto, embora seja verdade que A seja executado no tempo polinomial e seja verdade que A resolva o 3-SAT, pelo menos um desses fatos não pode ser comprovado. O 3-SAT existe não implica que um "possa ser encontrado".
David Richerby
Portanto, o "Mas se nenhum exemplo de solução polinomial para um problema completo de NP puder ser encontrado, isso significa que P = NP é falso" está errado, porque pode haver uma solução mesmo que não possa ser encontrada?
Alvaro
Está correto.
David Richerby
3
McNnNnMnc
5

Tpecatte
fonte