Provando P = NP sem declarações matemáticas / programa de computador

Este é o meu primeiro post depois de ser um usuário passivo há algum tempo. Desejo fazer algumas perguntas, se puder. Eu não sou um matemático, mas minha pergunta se refere ao campo da matemática / ciência da computação. Em particular, o problema P vs NP. Estou ciente de que esse é um problema que os profissionais de elite ainda não conseguiram resolver ...

Independentemente disso, gostaria de perguntar:

Se uma pessoa que não é um matemático nem um programador venha a apresentar um fluxograma ou uma série de etapas escritas em inglês básico que supostamente fornecem uma solução para um dos problemas P vs NP, isso seria considerado como 'prova' de que P = NP .. para reivindicar o prêmio do Clays Institute :)? Ou é necessário escrever a solução como provas matemáticas / programa de computador?

Obrigado.

"Não", você pode usar "inglês básico".

Se você tivesse sucesso, teria criado uma prova construtiva . As provas em matemática costumam ser uma mistura de "inglês básico", como você chama e fórmulas matemáticas, mas elas também não precisam conter uma prova válida.

Suponha que você tenha esse fluxograma, o que você precisa provar - ou seja, argumentar - é que seu algoritmo funciona para todas as instâncias de problemas. A maneira como você faz isso depende inteiramente de você, desde que a prova seja inequívoca e todas as premissas que você afirma tenham se mostrado verdadeiras.

Feito isso, você tem uma prova matemática em suas mãos. Então, realmente, eu deveria ter dito " Sim " no começo, você precisa de uma prova matemática .

Uma máquina de Turing, é preciso lembrar, é uma espécie de fluxograma. Assim é a estrutura de um programa de computador em geral. Portanto, transformar "um fluxograma" em uma resposta formal ao problema deve ser bastante fácil, se realmente funcionar. De fato, se alguém começasse com uma resposta terrivelmente formal a P versus NP , a maioria dos cientistas da computação tentaria encontrar uma formulação que fosse o mais próxima possível de uma descrição simples em inglês, a fim de obter uma compreensão tão forte da solução quanto possível. possível.

Mas há um problema fundamental com o tipo de pergunta que você está fazendo. O que significa para alguém que seria capaz de resolver P versus NP - e mostrando que eles são iguais, não menos - não ser realmente um cientista da computação ou um matemático? Talvez eles não sejam empregados profissionalmente como cientista da computação ou matemático, mas isso não vem ao caso se eles tiverem a habilidade de resolver o que alguns (Scott Aaronson, por exemplo) descrevem como o problema matemático mais importante que já consideramos. Se alguém tem o treinamento (ou até mesmo autodidata) para resolver o problema com sucesso e também comunicar claramente a solução a outras pessoasidentificando as principais sub-rotinas e seus papéis na solução, por exemplo, SAT ou HAMPATH, se eles estão empregados ou têm diplomas é um detalhe irrelevante; são, no entanto, nesse caso um matemático ou um cientista da computação. Melhor ainda, se eles puderem descrever como suas soluções superam obstáculos clássicos, como resultados de oráculos, como oráculos A, para os quais P ^A ≠ NP ^A (ou o oposto), mostrando especificamente que tipos de estrutura no problema o algoritmo tira proveito, quais não seria acessível no modelo oracle. O problema, no entanto, é que a maioria das pessoas que sonha em resolver P versus NP como amadores ou forasteirosparecem não ter habilidades de comunicação para descrever seu trabalho adequadamente, ou (em virtude de não terem lido o suficiente) desconhecem os resultados que tornariam sua abordagem para resolver o problema condenada desde o início.

Como em todos os sonhos de glória nos dias de hoje, existe um problema básico com a fantasia de ser o único a resolver P versus NP . O problema é que é quase impossível. Na verdade , não é impossível, lembre-se, ou pelo menos não necessariamente impossível; quase isso. Como alguém brilhante com ambição, é possível perder de vista o fato de que existem muitas outras pessoas brilhantes: muitas das quais também pensaram no problema; e muitos dos quais são mais brilhantes do que eles mesmos, mesmo por algumas ordens de magnitude. E que tem havido pessoas tão brilhantes enquanto o problema existe; e ainda permanece sem solução. Sim, é possível, em princípio, que todo mundo esteja pensando sobre o assunto de maneira errada, e há décadas. Mas é issorealmente particularmente provável? Ninguém deve esperar ser a única pessoa que pode identificar o único erro de sinal que todo mundo está cometendo, porque se todo mundo está cometendo esse erro, deve haver algo sobre o problema que o levará a cometer o mesmo erro. Ou - no caso mais provável de que a razão pela qual o problema permaneça não resolvido não sejaque as pessoas continuam cometendo erros simples ou ainda não pensaram no único truque simples que dissolve a coisa toda - o que torna o problema fundamentalmente difícil é essencialmente uma dificuldade objetiva do problema, e nenhum passo de dança inteligente permite que se salte graciosamente passado todos os obstáculos; que o que é necessário é uma abordagem que não seja apenas nova, mas bastante profunda, identificando estruturas sutis que havia boas razões para ninguém ter visto antes. O tipo de estrutura que é mais provável que você encontre pensando continuamente sobre o problema por anos.

Se você quiser ser realista sobre o que seria necessário para resolver o problema P versus NP , você pode compará-lo com descobertas igualmente famosas nas últimas décadas, como as provas do teorema das quatro cores, o Último Teorema de Fermat ou o Conjectura de Poincaré. Eles podem ter provas mais simples um dia, mas as provas originais levam você para longe no deserto para chegar até o fim (ou no caso do teorema das Quatro Cores, a rota é muito longa e repetitiva). Não há nenhuma razão particular para suspeitar que P versus NP será diferente; de modo que, no final, éresolvidas por um amador, as chances são extremamente grandes de que alguém com conhecimento e experiência similares em conhecimento de técnicas de alguém que seja treinado academicamente. Qualquer amador realista que sonha em resolver P versus NP faria bem em manter isso em mente.

Uma prova de que P = NP pode ser aceito por um periódico matemático, mas nunca será aceito pelos profissionais de elite. A razão é que eles sabem que P! = NP (pelo menos para todos os fins práticos). Eles também sabem que é inacreditavelmente difícil provar isso, portanto, mesmo uma prova de que P! = NP será recebida com uma quantidade saudável de ceticismo pelos profissionais de elite.

Os profissionais de elite têm razões mais elaboradas do que muitas mentes brilhantes tentaram e falharam em construir um algoritmo polinomial para NP ou provar N! = NP. No entanto, eles esperam razoavelmente que esse argumento seja o mais convincente para um leigo. Provavelmente, eles estão certos que a referência a barreiras relacionadas a provas de relativização, provas naturais ou provas de algebrização raramente é convincente para um não especialista. Se muitos "amadores" tentarem resolver P vs NP de uma certa maneira (por exemplo, por resolução lógica ou reduzindo-o a um problema de programação linear), alguém passará por dificuldades (isso às vezes leva anos) para provar que esse ângulo específico de ataque provavelmente está fadado ao fracasso.

Editar Estou encantado que esta resposta continue a atrair feedback (negativo). Permita-me, portanto, substituir a segunda parte da resposta (que parece não ter relação com o feedback, mas pode desviar o foco do ponto principal) pela seguinte citação de Truth vs Proof :

Poderíamos permanecer agnósticos, dizendo que simplesmente não sabemos, mas pode haver ceticismo em demasia na ciência. Por exemplo, Scott Aaronson certa vez afirmou que em outras ciências P! = NP já teria sido declarada uma lei da natureza. Eu tendem a concordar. Afinal, estamos tentando descobrir a verdade sobre a natureza da computação e essa busca não será mais rápida se insistirmos em descartar toda evidência que não esteja na forma de provas matemáticas dos primeiros princípios.

Essa alteração não visa reduzir a quantidade de feedback, mas deixar perfeitamente claro que essa resposta é séria sobre o fato de que os especialistas "sabem que P! = NP", mesmo assim não podem provar isso.

23 de novembro de 2013 Obrigado novamente por todos os comentários. Para o registro, a resposta agora tem 7 votos negativos, 1 voto positivo e 14 comentários (8 por mim). Devido à quantidade de comentários, as referências e justificativas interessantes estão ocultas, então decidi adicionar algumas delas aqui:

• Como o próprio Gödel escreveu a von Neumann, se P = NP fosse verdadeiro "para todos os fins práticos", seu teorema da incompletude seria verdadeiro apenas na teoria, mas efetivamente falso na prática.

• Em seu artigo de 1971, Stephen Cook ... incapaz de produzir contra-exemplos para o procedimento de Davis-Putnam (resolvido por Haken 1985). Hoje, muitas técnicas, resultados e contra-exemplos estão disponíveis para "refutar" os solucionadores de NP eficientes propostos. Também P = NP contradiz a "lei da conservação da dificuldade", a correspondência "qualitativa infinita <-> quantitativa quantitativa", ...

• Há muito tempo, Scott Aaronson escreveu este comentário :

  anônimo: Você afirma (como fato!) que 3SAT é uma linguagem no NP que não pode ser calculada em tempo polinomial. Mas você não pode provar isso. Esse é o seu método científico? Sim. Como firme crente na ciência e na razão, luto para distinguir claramente entre o que posso provar e o que apenas sei que é verdade.

• Scott é famoso por tentar demonstrar o que significa "saber" alguma coisa, por exemplo, apostando US $ 200.000: scottaaronson.com/blog/?p=458