O Problema P versus NP

O problema P versus NP questiona se todo problema cujas soluções podem ser verificadas rapidamente também pode ser resolvido rapidamente, sendo a questão central em aberto da ciência da computação teórica e um dos problemas do Prêmio Millennium Clay.

Definition

P é a classe de problemas solúveis em tempo polinomial, e NP a classe de problemas cujas soluções propostas são verificáveis em tempo polinomial; o problema P versus NP questiona se essas duas classes são iguais, o que ocorre se e somente se algum problema NP-completo for solúvel em tempo polinomial.

Scope

Este tópico abrange a declaração formal de P versus NP, sua equivalência a se qualquer problema NP-completo possui um algoritmo de tempo polinomial, as consequências de qualquer uma das respostas, as barreiras como relativização, provas naturais e algebrização que bloquearam o progresso, e a conjectura generalizada de que as classes são diferentes.

Core questions

• Encontrar uma solução é fundamentalmente mais difícil do que verificá-la?
• Por que a resposta depende de se algum problema NP-completo está em P?
• Como seria o mundo se P fosse igual a NP, e se não fosse?
• Por que décadas de esforço falharam em resolver a questão?

Key theories

Equivalência à NP-completude

P é igual a NP se e somente se qualquer problema NP-completo tiver um algoritmo de tempo polinomial, de modo que a questão abrangente se reduz à tratabilidade de um único problema concreto, como a satisfatibilidade.

Barreiras de prova

Resultados de relativização, provas naturais e algebrização mostram que as principais técnicas de prova conhecidas não podem resolver P versus NP, explicando a dificuldade e guiando a busca por métodos fundamentalmente novos.

Clinical relevance

A presumida desigualdade de P e NP é a suposição de trabalho por trás de tratar problemas NP-difíceis como intratáveis e por trás da segurança da criptografia, uma vez que a resolução eficiente de problemas NP quebraria a criptografia amplamente utilizada; uma prova construtiva de que P é igual a NP transformaria a otimização, a logística e a ciência.

History

Cook formulou a questão em 1971, juntamente com a NP-completude, e ela foi rapidamente reconhecida como fundamental. Tentativas via limites inferiores de circuitos na década de 1980 encontraram a barreira das provas naturais identificada por Razborov e Rudich, e em 2000 o Clay Mathematics Institute a nomeou um problema do Prêmio Millennium com um prêmio de um milhão de dólares.

Debates

O problema P versus NP será algum dia resolvido, e qual é a resposta?

A maioria dos pesquisadores conjectura que P não é igual a NP, mas nenhuma prova existe e as técnicas conhecidas são comprovadamente insuficientes. As opiniões divergem sobre se a resolução está próxima, requer matemática radicalmente nova, ou se a questão pode até ser independente dos axiomas padrão.

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp
• Alexander Razborov

Seminal works

• cook1971
• aroraBarak2009

Frequently asked questions

O que aconteceria se P fosse igual a NP?

Muitos problemas agora considerados intratáveis, desde o agendamento ideal até a quebra de códigos criptográficos, teriam algoritmos eficientes, e o ato de encontrar soluções não seria mais difícil do que verificá-las. Os efeitos no comércio, segurança e ciência seriam profundos, o que é parte do motivo pelo qual a maioria dos especialistas espera que P não seja igual a NP.

Por que o problema é tão difícil de resolver?

Provar que P é igual a NP requer um algoritmo rápido para um problema NP-completo, que ninguém encontrou; provar que eles diferem requer mostrar que tal algoritmo não pode existir. Resultados sobre relativização e provas naturais demonstram que as técnicas padrão são inerentemente incapazes de estabelecer o último, então uma abordagem genuinamente nova é necessária.