A prova de Vinay Deolalikar de que P é diferente de NP procede?

Responder essa vai ser bem difícil, viu.

O Deolalikar usa um monte de coisas de um monte de áreas diferentes e um possível erro pode estar escondido em qualquer lugar. Eu confesso que, em uma primeira leitura, mal entendi o abstract.

Pelo menos ele é um cara de algum renome, e a prova dele parece bem mais séria do que algumas que eu já vi.

Bom, isso não quer dizer que ela não deva estar aqui. Pensando no Umamão como um repositório de conhecimento para estudantes, me parece muito adequado que essa discussão apareça aqui...

É, e a pergunta pode começar meio verde assim, e conforme vão saindo notícias a respeito (gente que verificou a prova, etc.), ela vai sendo melhorada, amadurecendo (qualquer comparação descarada com um mamão é mera coincidência :P)

Eu não diria que o Deolalikar tem renome na área de complexidade. Nos últimos 10 anos ele só tem uma publicação nesta área. Eu (e grande parte da comunidade) com certeza esperaria alguém com uma bagagem maior. Mas casos de outsiders que resolvem problemas importantes são conhecidos, mesmo que muito raros na matemática.

Eu não quis dizer que a pergunta não é adequada. Meu comentário foi só pra expor o que eu sabia, o que não daria uma resposta. Quanto ao renome, o que eu quis dizer é que ele é conhecido, não como pesquisador em complexidade, mas como pesquisador em computação. Essa seria uma evidência da seriedade do trabalho, e que não seria só para chamar a atenção.

Não seria melhor fazer dessa questão Community Wiki?

Um primeiro passo pra compreender a prova do Deolalikar é estudar o trabalho que a galerinha de IA tem feito sobre o limite entre problemas de satisfatibilidade fáceis e difíceis, que nos leva aos problemas de satisfação de restrições.

Em 2005, saiu um artigo na Nature entitulado "Can Get Satisfaction" - http://www.cs.cornell.edu/gomes/papers/gs-nature-05.pdf

Pra dar um passeio curto nesse assunto, a satisfação de restrições trabalha com formulações alternativas para problemas combinatórios e métodos de busca de soluções. É como programação inteira, mas valorizando especificidades.

A questão sobre número de publicações é um pouco irrelevante. Em teoria, publica-se bem menos. Na verdade, isso até fala a favor dele, já que um trabalho anterior provou que a linguagem dos problemas P é menor que a linguagem dos problemas NP em máquinas de Turing infinitas. A seriedade dessa prova partiu do fato que ele já tinha apresentado esse pequeno resultado anterior.

Nessa questão de satisfatibilidade, entram uns assuntos interessantes como variáveis backdoor: em um problema de satisfação, é o conjunto mínimo de variáveis que, se fixadas, fazem com que o problema restante seja fácil. Pegando um exemplo simples (não sei se backdoor, mas certamente sobre a fronteira fácil-difícil): quando você estuda problemas que podem ser decompostos em restrições binárias, é possível montar um grafo de restrições com nós sendo variáveis e restrições sendo arcos. Se esse grafo for uma árvore, é fácil encontrar uma solução para o problema ou certificar que ela não existe.

Em resumo, o que eu entendi da prova é que ele estuda a estrutura dessas relações entre variáveis nos problemas P e NP-Completo. Baseado em propriedades do 3SAT, ele conclui que existem problemas NP que não estão em P.