Foi publicada semana passada uma prova para o famoso problema P=NP(?). Para conseguir resolver o problema, usou-se até teoria de Física Estatística. Abaixo segue a tradução do resumo (abstract) do artigo.A prova foi feita por Vinay Deolalikar (foto), um pesquisador da HP Labs.
O artigo original pode ser baixado no link abaixo:
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf
Se tudo estiver correto, Vinay ganhará o prêmio merecido de 1 milhão de dólares, já que o problema está listado como um dos 7 problemas de 1 milhão de dólares (http://pt.wikipedia.org/wiki/Problemas_do_Prêmio_Millenium).
----------
Resumo
Nós demonstramos a separação da classe de complexidade NP da sua subclasse P. Ao longo da nossa prova, observamos que a capacidade de calcular a propriedade sobre as estruturas em tempo polinomial está intimamente relacionado às noções de estatística de independência condicional e estatísticas suficientes. A presença de independências condicionais manifesta sob a forma de parametrizações econômica da distribuição conjunta de covariáveis. Para aplicar essa análise para o espaço de soluções de problemas de satisfação com restrições aleatórias, nós utilizamos e expandimos ideias de diversos campos que abrangem lógica, estatística, modelos gráficos, conjuntos aleatórios e física estatística.
Começamos por introduzir o necessário quadro de modelos gráficos para um conjunto de variáveis que interagem. Nós nos concentramos sobre a correspondência entre Markov e propriedades de Gibbs para modelos diretos e indiretos como refletidos na fatoração de sua distribuição conjunta, e o número de parâmetros independentes necessários para especificar a distribuição.
Em seguida, construímos a contribuição central deste trabalho. Nós mostramos que há relações conceituais fundamentais entre a computação em tempo polinomial, o qual é completamente capturado pela lógica FO(LFP) em algumas classes de estruturas e algumas propriedades de Markov diretas em termos de independência condicional e estatística suficientes. A fim de demonstrar essas relações, nós vemos um cálculo LFP como "fatorando através de" diversas etapas dos cálculos de primeira ordem, e depois utilizar as limitações da lógica de primeira ordem. Especificamente, nós exploramos a limitação de que a lógica de primeira ordem só pode expressar as propriedades em termos de um número limitado de vizinhanças locais da estrutura fundamental.
Em seguida, apresentamos ideias a partir da quebra de simetria de réplicas 1RSB "ansatz" de física estatística. Nós lembramos a descrição da fase aglomerada do d1RSB para o k-SAT aleatório, que surge quando a densidade da cláusula é suficientemente elevada. Nesta fase, uma fração arbitrariamente grande de todas as variáveis em núcleos congelam dentro de exponencialmente muitos clusters no limite termodinâmico, como a densidade de cláusula é aumentada para o limiar SAT-unSAT para k suficientemente grande. A distância de Hamming entre uma solução que consiste em um cluster e que está em outro é O(n).
Em seguida, codificamos fórmulas k-SAT como estruturas em que FO(LFP) captura tempo polinomial. Ao pedir a FO(LFP) para ampliar as atribuições parciais em conjuntos aleatórios de k-SAT, vamos construir as distribuições das soluções. Em seguida, construímos um modelo gráfico dinâmico em um espaço do produto que capta toda a informação que flui através das várias fases de um cálculo de um LFP sobre conjuntos de estruturas k-SAT. Distribuições calculadas por LFP devem satisfazer este modelo. Este modelo é direcionado, o que nos permite calcular fatorações localmente e parametrizar usando potenciais de Gibbs em cliques. Em seguida, usamos os resultados de conjuntos de gráficos de fator aleatório k-SAT para limitar os diversos fluxos de informação no modelo gráfico direcionado. Nós parametrizamos as distribuições resultantes de uma forma que demonstra que as interações irredutíveis entre covariáveis - ou seja, aqueles que não podem ser fatorados a não ser através de independências condicionais - não podem crescer mais rápido do que poly(logn) nas distribuições LFP calculadas. Esta caracterização permite-nos analisar o comportamento de toda a classe de algoritmos de tempo polinomial em conjuntos simultaneamente.
Usando as já citadas limitações de LFP, demonstramos que uma solução em tempo polinomial para k-SAT resultaria em espaço de solução que é uma mistura de distribuições cada uma com uma parametrização exponencialmente menor do que é coerente com as fases d1RSB altamente restritas do k-SAT. Nós mostramos que isto estaria em contradição com o comportamento exibido pelo espaço de soluções na fase d1RSB. Isso corresponde à figura intuitiva fornecida pela física sobre a emergência das extensas (significango O(n)) correlações de longo alcance entre as variáveis nesta fase e também explica a observação empírica de que todos os conhecidos algoritmos de tempo polinomial param nesta fase.
Nosso trabalho mostra todo algoritmo de tempo polinomial pode falhar em produzir soluções para instâncias de problema suficientemente grandes de k-SAT na fase d1RSB. Isso mostra que os algoritmos de tempo polinomial não são capazes de resolver problemas NP-completos em suas fases difíceis, e demonstra a separação de P e NP.
----------
Saiba mais sobre o problema:
http://pt.wikipedia.org/wiki/P_versus_NP
Atualização
A propósito, o amigo Álinson Santos indicou o site abaixo, onde já existem listadas quase 60 provas sobre o assunto (algumas provando que P=NP, e outras provando justamente o contrário).
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
