O problema "P versus NP" é o principal problema aberto da Ciência da Computação. Possui também enorme relevância em campos que vão desde a Engenharia até a criptografia aplicada aos serviços militares e às transações comerciais e financeiras via Internet.
Definição do problema
De modo simplificado, o problema pergunta se existem problemas matemáticos cuja resposta pode ser verificada em tempo polinomial, que não possam ser resolvidos (diretamente, sem se ter um candidato à solução) em tempo polinomial. Ilustrando: se alguém lhe disser que o número 13.717.421 pode ser escrito como o produto de dois outros inteiros, você provavelmente demorará para provar isso; contudo, se lhe assoprarem que ele é o produto de 3.607 por 3.803, você seria capaz de muito rapidamente verificar tal fato.
O problema "P versus NP" parte da constatação que são muito frequentes as situações em que parece ser muito mais rápido verificar solução do que achar um processo de resolução, e então pergunta: isso sempre ocorre, ou simplesmente ainda não descobrimos um modo de resolvê-los rapidamente?
Para uma discussão mais desenvolvida, mas ainda evitando tecnicalidades, sobre o Problema "P versus NP", veja outro problema clássico: o problema do caixeiro viajante.
Sua importância resume-se em duas capacidades: de modo simples e concreto, exemplifica a enorme velocidade de crescimento da fatorial; prova-se que muitos problemas combinatórios envolvem tantas alternativas de solução quanto este problema, de modo que ele é uma espécie de métrica com a qual medimos a complexidade computacional dos problemas combinatórios ocorrendo em engenharia e no trabalho científico.
Contexto
A relação entre as classes de complexidade P e NP é estudada na teoria da complexidade computacional, parte da teoria da computação que lida com os recursos necessários computacionais para se resolver um determinado problema. Os recursos mais comuns são o tempo (quantos passos é preciso para se resolver um problema) e espaço (a quantidade de memória necessária para se resolver um problema). Em tal análise, um modelo de computador cujo tempo deve ser analisado é necessário. Geralmente, esses modelos assumem que o computador é determinístico (dado o estado atual do computador e todas as entradas, há apenas uma ação possível que o computador pode realizar) e sequencial (executa ações uma após a outra).
Nesta teoria, a classe P consiste em todos os problemas de decisão (definidos abaixo) que podem ser resolvidos por uma máquina determinística sequencial em uma quantidade de tempo que é polinomial para o tamanho da entrada; a classe NP consiste em todos os problemas de decisão cujas soluções positivas podem ser verificadas em tempo polinomial dada a informação correta, ou de forma análoga, cujas soluções podem ser encontradas em tempo polinomial em uma máquina não determinística. Claramente, P ⊆ NP. Sem dúvida a maior questão sem respostas na ciência da computação teórica se diz respeito à relação entre essas duas classes: P é igual a NP?
NP-completo
Para atacar a questão P = NP, o conceito de NP-completude é muito útil. Problemas NP-completos são um conjunto de problemas que podem ser reduzidos em tempo polinomial a partir de qualquer outro problema NP, mas cuja solução ainda pode ser verificada em tempo polinomial. Informalmente, um problema NP-completo é pelo menos tão difícil quanto qualquer outro problema NP. Problemas NP-difíceis são aqueles ao menos tão difíceis quanto problemas NP-completos, ou seja, todos os problemas NP podem ser reduzidos (em tempo polinomial) para NP-difíceis. Problemas NP-difíceis não precisam estar em NP, ou seja, eles não precisam ter soluções verificáveis em tempo polinomial.
Por exemplo, a versão do problema de decisão do caixeiro viajante é NP-completo, portanto, qualquer instância de qualquer problema em NP pode ser transformada mecanicamente em uma instância do problema do caixeiro viajante, em tempo polinomial. O problema do caixeiro viajante é um dos muitos problemas NP-completos. Se qualquer problema NP-completo está em P, então sabe-se que P=NP. Infelizmente, muitos problemas importantes foram mostrados serem NP-completos, e até 2018 nenhum algoritmo rápido para qualquer um deles foi descoberto.
Só com base na definição não fica claro que problemas NP-completos existem. Um trivial e artificial problema NP-completo pode ser formulado como: dada uma descrição de uma máquina de Turing M garantida para parar em tempo polinomial, existe um polinômio de entrada de tamanho M que será aceito? Este problema está em NP porque (dando uma entrada) é simples de se verificar se M aceita ou não a entrada através de uma simulação de M; é NP-completo porque o verificador para qualquer instância particular de um problema em NP pode ser codificado como uma máquina M em tempo polinomial que toma a solução para ser verificada como entrada. Então, a questão é saber se existe ou não uma instância determinada por uma entrada válida.
O primeiro problema provado ser NP-completo foi o Problema de Satisfatibilidade Booleana (SAT). Ele passou a ser conhecido como o teorema de Cook-Levin; ele prova que satisfatibilidade, que é NP-completo, contém detalhes técnicos sobre máquinas de Turing e mostra como esses detalhes se relacionam com a definição de NP. No entanto, após este problema ser provado ser NP-completo, pela prova da redução previa-se de maneira simples que vários outros problemas estariam nessa classe. Assim, uma vasta classe de problemas aparentemente não relacionados seriam todos redutíveis uns aos outro, e seriam de alguma forma “o mesmo problema”.
Problemas mais difíceis
Embora não se saiba se P ≠ NP, problemas fora de P são conhecidos. Uma série de problemas sucintos (problemas que não operam na entrada normal, mas na descrição computacional da entrada) são conhecidos por serem EXPTIME-completo. Por causa disso, pode ser mostrado que problemas P EXPTIME estão fora de P, e assim exigem um tempo maior do que um tempo polinomial. De fato, pelo teorema da Hierarquia de Tempo, eles não podem ser resolvidos em tempo significativamente menor do que exponencial. Exemplos incluem a busca de uma estratégia perfeita para o xadrez (um N X N) e alguns outros jogos de tabuleiro.
O problema de decidir a verdade de uma declaração na aritmética de Presburger requer ainda mais tempo. Fischer e Rabin, em 1874 provaram que todo algoritmo que decide a verdade de declarações na aritmética de Presburger tem um tempo de execução de, pelo menos, 2^2cn menor que uma constante c, sendo n o comprimento da declaração. Assim, o problema é conhecido por precisar de mais tempo do que uma execução exponencial. Ainda mais difícil são os problemas indecidíveis, tais como o Problema da Parada. Eles não podem ser completamente resolvidos por nenhum algoritmo, no sentido de que para qualquer algoritmo, há pelo menos uma entrada para a qual o algoritmo não irá produzir a resposta certa; ele tenderá a produzir uma resposta errada, terminar sem dar nenhuma resposta conclusiva ou caso isso não ocorra, produzir qualquer resposta.
Problemas em NP não conhecidos em P ou NP-completo
Latner mostrou que se P ≠ NP então existem problemas em NP que não estão nem em P nem em NP-completo. Esses problemas são chamados Problemas intermediários da NP. O problema do isomorfismo gráfico, o problema do Logaritmo Discreto e o problema da Fatoração de Números Inteiros são exemplos de problemas que acredita-se que sejam NP-intermediários. Eles são alguns dos muito poucos problemas de NP que não se sabe se são em P ou se são NP-completo.
O problema do isomorfismo gráfico é o problema computacional que determina se dois gráficos finitos são isomórficos. Um importante problema não resolvido na teoria da complexidade é se o problema do isomorfismo gráfico está em P, NP-completo ou NP-intermediário. A resposta é desconhecida, mas acredita-se que, ao menos, o problema é não é NP-completo. Se o isomorfismo gráfico é NP-completo, a hierarquia do tempo polinomial entra em colapso com o segundo nível. Uma vez que acredita-se amplamente que a hierarquia polinomial não entra em colapso com qualquer nível finito, acredita-se que o isomorfismo gráfico não é NP-completo. O melhor algoritmo para este problema, graças a Laszlo Babai e Eugene Luks tem tempo de execução 20(√(n log n)) para gráfico com n vértices.
O problema da fatoração de inteiros é o problema computacional de determinar a fatoração de primos de um inteiro dado. Estabelecido como um problema de decisão, é o problema de decidir se a entrada tem um fator menor que k. Nenhum algoritmo de fatoração inteiro eficiente é conhecido, e este fato forma a base de vários sistemas criptográficos modernos, como o algoritmo RSA. O problema da fatoração do inteiro está na NP e na co-NP (ou até na UP e na co-UP). Se o problema é NP-completa, a hierarquia de tempo polinomial vai entrar em colapso com seu primeiro nível. (isto é, NP = co-NP). O melhor algoritmo conhecido para a fatoração de inteiro é a General Number Field Sieve (GNFS), que leva o tempo esperado para o fator de um n-bit inteiro. No entanto, o melhor algoritmo quântico conhecido por este problema, o algoritmo de Shor, é executado em tempo polinomial. Infelizmente, este fato não diz muito sobre onde o problema está em relação a classes de complexidade não-quânticas.
P significa “fácil”?
Toda a discussão acima tem dito que P significa "fácil" e "não em P" significa "difícil", uma hipótese conhecida como tese de Cobham. É uma hipótese comum e razoavelmente exata em teoria da complexidade, porém tem algumas ressalvas.
Primeiro, nem sempre é verdade na prática. Um algoritmo polinomial teórico pode ter muitos fatores constantes ou expoentes, tornando-o, assim, impraticável. Por outro lado, até mesmo se um problema se mostrar NP-completo, e mesmo se P ≠ NP, ainda pode haver abordagens eficazes para combater o problema na prática. Existem algoritmos para muitos problemas NP-completos, como o Problema da Mochila, o Problema do Caixeiro Viajante e o Problema de Satisfatibilidade Booleana, que podem resolver com otimização muitas instâncias do mundo real, em tempo razoável. A complexidade empírica da média de casos (tempo versus tamanho do problema) de tais algoritmos pode ser surpreendentemente baixa. Um exemplo famoso é o algoritmo simplex na programação linear, que funciona surpreendentemente bem na prática, apesar de ter pior caso de complexidade de tempo exponencial que anda junto com os mais conhecidos algoritmos de tempo polinomial.
Segundo, existem tipos de cálculos que não são compatíveis ao modelo de máquina de Turing em que P e NP são definidos, assim como computação quântica e algoritmos randomizados.
Razões para acreditar que P ≠ NP
De acordo com uma pesquisa, muitos cientistas da computação acreditam que P ≠ NP. A principal razão para essa crença é que, após décadas estudando estes problemas, ninguém foi capaz de encontrar um algoritmo de tempo polinomial para qualquer um dos mais de 3000 problemas NP-completos conhecidos. Esses algoritmos foram procurados muito antes do conceito de NP-completude ter sido definido (21 problemas NP-completos de Karp, entre os primeiros encontrados, eram todos problemas bem conhecidos existentes no momento em que foram mostrados para ser NP-completo). Além disso, o resultado P = NP implicaria em muitos outros resultados surpreendentes que estão acredita-se serem falsos atualmente, como NP = co-NP e P = PH.
Também é intuitivamente argumentado que a existência de problemas que são difíceis de resolver, mas para os quais as soluções são fáceis de verificar, combinam com a experiência do mundo real.