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?
fonte
Respostas:
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.
fonte
fonte