A prova de Deolalikar de 2010 de que

8

Recentemente, houve uma prova de queP≠NP . Pouco tempo após sua publicação, foram levantados alguns problemas com essa prova.

Então ... a prova está correta ou não? (Por favor, responda somente se você tiver evidências ... essa pergunta pode demorar um pouco até ser respondida)

np-hardness cc.complexity-theory ripper234
fonte
por que o voto para fechar?
Suresh Venkat
7
Penso que a pergunta deve especificar a que prova se refere (pelo menos mencione o nome do autor). Está claro agora, mas pode não estar claro daqui a um ano.
Moritz
2
Na IMO, você deve solucionar certas falhas em potencial na prova. Votou para fechar por causa da falta de especificidade da pergunta (a qualidade das postagens).
2
O link se refere à história recente, embora eu prefiro o link OP ao wiki polímata ou página da Deolalikar do que um post slashdot que parece menos permanente
Suresh Venkat

Respostas:

20

Em uma palavra: Não.

Parece que existem algumas falhas fatais na prova proposta por Deolalikar. A verdadeira questão agora é se a "prova" tem alguma idéia útil que possa ser construída. De qualquer forma, parece que a prova em sua forma atual simplesmente não está correta e também não pode ser corrigida. Por outro lado, Deolalikar não desistiu da prova, então acho que não é o fim.

Você pode encontrar uma atualização aqui: http://rjlipton.wordpress.com/2010/08/15/the-p%E2%89%A0np-proof-is-one-week-old/

Tomer Vromen
fonte
21

Veja o wiki .

Suresh Venkat
fonte