A questão P versus NP

Problema P versus NP

P versus NP é um dos maiores problemas não resolvidos em ciência da computação. Informalmente, ele pergunta se todo problema cuja solução pode ser verificada eficientemente por um computador também pode ser decidido por um computador de forma eficiente. Ele foi introduzido em 1971 por Stephen Cook em seu artigo seminal “A complexidade de procedimentos para a prova de teoremas” e é considerado por muitos como o problema mais importante da área. Ele é um dos sete Problemas do Prémio Millenium selecionados pelo Clay Mathematics Instiute que paga um milhão de dólares para a primeira solução correta.

Em essência, o problema P = NP pode ser reescrito pela seguinte pergunta: Suponha que as soluções para um problema possam ser verificadas rapidamente. Então, suas soluções podem ser calculadas rapidamente também? A noção teórica do termo “rapidamente” usado aqui significa um algoritmo que executa em tempo polinomial. A classe geral dos problemas para os quais algum algoritmo pode fornecer uma resposta em tempo polinomial é chamada de “classe P” ou apenas “P”. Para alguns problemas, não há nenhuma maneira conhecida para encontrar uma resposta rapidamente, mas se houver informação que mostre qual é a resposta, esta pode ser verificada rapidamente. A classe de problemas em que uma reposta pode ser verificada em tempo polinomial é chamada NP.

Considere o problema da soma de subconjuntos, um exemplo de problema que é fácil de ser verificado, mas que tem uma resposta difícil de ser calculada. Dado um conjunto de inteiros, existe um subconjunto não vazio tal que a soma dos seus elementos é igual a zero? Por exemplo, existe um subconjunto do conjunto {-2, -3, 15, 14, 7, -10} que some 0? A resposta é “sim, porque {-2, -3, -10, 15} somam 0”, resposta essa que rapidamente verificada. No entanto, não há algoritmo conhecido para encontrar tal subconjunto em tempo polinomial (existe um, porém em tempo exponencial, que consiste em 2n(2 elevado a n) – 1 tentativas) e de fato tal algoritmo não pode existir se as duas classes de complexidade não são as mesmas, daí este problema está em NP (verificada rapidamente), mas não necessariamente em P (decidida rapidamente).

Uma solução para o P = NP seria determinar se problemas como o problema da soma de subconjuntos que podem ser verificados em tempo polinomial também podem ser resolvidos em tempo polinomial. Se fosse provado que P não é igual a NP, significaria que há problemas em NP (problemas NP-completo) que são mais difíceis de resolver do que se verificar: eles não poderiam ser resolvidos em tempo polinomial, mas a resposta poderia ser verificada em tempo polinomial.

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ística (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 (definido 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?

Em uma pesquisa realizada em 2002 por 100 pesquisadores, 61 acreditavam que a resposta fosse não, 9 acreditavam que a resposta era sim e 22 não tinham certeza; 8 acreditavam que a questão pode ser independente dos axiomas aceitos atualmente e, portando impossível de se provar ou refutar.

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, pelo 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 para serem NP-completos, e até 2011 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: dado 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 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 das informações Presburger tem um tempo de execução de, pelo menos, 2^2cn menor que uma constante c. Aqui, n é o comprimento do statemente de Presburger. 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 alogaritmo 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 alogaritmo de fatoração inteiro eficiente é conhecido, e este fato forma a base de vários sistemas criptográficos modernos, como o alogaritmo 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 alogaritmo conhecido para a fatoração de inteiro é a General Numver Field Sieve (GNFS), que leva o tempo esperado O(e(64/9)1/3(n.log 2)1/3(log (n.log 2))2/3) 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 falha em relação a classes de complexidade não-quanticas.

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.

Se P = NP, então o mundo seria um lugar profundamente diferente do que supomos que ele seja. Não haveria nenhum valor especial em "saltos criativos," nenhuma lacuna fundamental entre resolver um problema e reconhecer a solução, uma vez que ele é encontrado. Todos que puderam apreciar uma sinfonia seria Mozart; todos que poderia seguir um argumento passo a passo seria Gauss ... - Scott Aaronson, MIT

Por outro lado, alguns pesquisadores acreditam que há excesso de confiança em acreditar que P ≠ NP e que os investigadores devem explorar provas de que P = NP também. Por exemplo, essas declarações foram feitas em 2002:

O principal argumento em favor da P ≠ NP é a total carência de progresso fundamental na área de busca exaustiva. Isto é, na minha opinião, um argumento muito fraco. O espaço de algoritmos é muito grande e nós estamos apenas no início de sua exploração. [. . .] A resolução do Último Teorema de Fermat mostra também que as questões muito simples podem ser resolvidos apenas por teorias muito profundas. -Moshe Y. Vardi, Rice University

Estar ligado a uma especulação não é um bom guia para o planejamento de pesquisa. Um deve sempre tentar ambas as direções de todos os problemas. O preconceito tem levado matemáticos famosos a falhar ao resolver problemas conhecidos cuja solução era oposta às suas expectativas, apesar de terem sido desenvolvidos todos os métodos necessários. -Anil Nerode, Cornell University

Consequências da resolução do problema

Uma das razões de o problema atrair tanta atenção são as conseqüências da resposta. Qualquer direção de resolução iria avançar a teoria enormemente, e talvez tenha enormes conseqüências práticas também.

P = NP

A prova de que P = NP poderia ter conseqüências práticas magníficas, se a prova levasse a métodos eficientes para resolver alguns dos importantes problemas na NP. Também é possível que uma prova não levaria diretamente para métodos eficientes, talvez se a prova não for construtiva, ou se o tamanho do polinômio delimitador for grande demais para ser eficiente na prática. As conseqüências, tanto positivas como negativas, originam-se desde que vários problemas NP-completos são fundamentais em muitos campos. Criptografia, por exemplo, depende de certos problemas sendo difíceis. Uma solução construtiva e eficiente para um problema NP-completo, tais como 3-SAT, iria quebrar a maioria dos sistemas de criptação (???) existentes, ´incluindo criptografia de chave pública, uma base para muitas aplicações de segurança modernos, como transações econômicas seguras através da Internet, e codificações simétricas, como AES ou 3DES, usadas para a criptografia de dados de comunicações. Estes teriam de ser modificados ou substituídos por soluções de informação teoricamente seguras.

Por outro lado, há enormes conseqüências positivas que poderiam acompanhar a representação tratável muitos problemas atualmente matematicamente intratáveis. Por exemplo, muitos problemas em pesquisas de operações são NP-completo, tais como alguns tipos de programação inteira, é o problema do CAIXEIRO VIAJANTE, para citar dois dos exemplos mais famosos. Soluções eficazes para esses problemas teriam enormes implicações para logísticas. Muitos outros problemas importantes, como alguns problemas na previsão da estrutura de proteínas, também são NP-completos; se estes problemas fossem eficiente resolvíveis, poderiam estimular avanços consideráveis na biologia.

Mas tais mudanças podem enfraquecer significativamente se comparadas à revolução de um método eficiente para a resolução de problemas NP-completos poderia causar na própria matemática. De acordo com Stephen Cook, ... seria transformar a matemática, deixando que um computador encontre uma prova formal de qualquer teorema que tem uma prova de um tamanho razoável, uma vez que as provas formais podem ser facilmente reconhecidas em tempo polinomial. Problemas-exemplo podem muito bem incluir todos os problemas-prêmio CMI.

Pesquisadores matemáticos gastam suas carreiras tentando provar teoremas, e algumas provas têm levado décadas ou mesmo séculos para serem decifradas - por exemplo, o Último Teorema de Fermat levou mais de três séculos para ser provado. Um método que fosse garantido para encontrar provas de teoremas deveria existir de um tamanho "razoável". Iria essencialmente acabar com essa luta.

P ≠ NP

A prova que mostrou que P ≠ NP faltaria os benefícios práticos computacionais de um prova de que P = NP, mas que, no entanto, representam um avanço muito significativo na teoria da complexidade computacional e fornecer orientações para pesquisas futuras. Permitiria mostrar de uma maneira formal de que muitos problemas comuns não podem ser resolvidos de forma eficiente, de modo que a atenção de pesquisadores pode ser focado em soluções parciais ou soluções para outros problemas. Devido à crença generalizada em P ≠ NP, grande parte desse foco de pesquisa já foi realizada.

P ≠ NP também ainda deixa aberta a complexidade média-caso de problemas difíceis em NP. Por exemplo, é possível que SAT requeira tempo exponencial no pior caso, mas que quase todas as instâncias selecionadas aleatoriamente de que são resolução eficiente. Russell Impagliazzo descreveu cinco hipotético "mundos" que poderia resultar das diversas soluções possíveis para a questão caso a complexidade da média. Estes vão desde "Algorithmica", onde P = NP e problemas como SAT pode ser resolvido de forma eficiente em todas as instâncias, para "Cryptomania", onde P ≠ NP e gerando casos de problemas de difícil fora P é fácil, com três possibilidades intermediárias refletindo diferentes distribuições possíveis de dificuldade mais casos de problemas NP-difíceis. O "mundo" onde P ≠ NP, mas todos os problemas em NP são tratáveis ​​no caso médio é chamado de "Heuristica" no papel. A Princeton University oficina em 2009 estudou a situação dos cinco mundos.

Algoritmo de tempo polinomial

Nenhum algoritmo para qualquer problema NP-completo é conhecido para ser executado em tempo polinomial. No entanto, existem algoritmos para problemas NP-completo com a propriedade que se P = NP, então o algoritmo é executado dentro do tempo polinomial (embora com constantes enormes, tornando o algoritmo impraticável). O algoritmo a seguir, devido à Levin, é um exemplo. Corretamente aceita a linguagem NP-completo SUBSET-SUM, e executado em tempo polinomial se e somente se P = NP.

// Algoritmo que aceita a linguagem NP-completa SUBSET-SUM // // Esse é um algoritmo de tempo polynomial se e somente se P = NP. // // “Tempo-polinomial" significa retornar sim dentro do tempo // polinomial quando a resposta deveria ser “sim”, e executar // infinitamente quando for “não”. // // Entrada: S = a conjunto finite de inteiros // Saída: "sim" se qualquer se qualquer subconjunto de S acrescenta-se a 0 // Executa infinitamente quando a saída for não, por outro lado. // Nota: "program number P" é um programa obtido por // escrever o inteiro P em binário, então // considerar que a string de bits pode ser um // programa. Todo programa possível pode ser // gerado desta maneira, embora a maioria não faz nada // por erro de sintaxe. // //Para N = 1...infinito // Para P = 1...N // Executar o program number P por N etapas com entrada S // Se a saída do programa for uma lista distinta de inteiros // E os inteiros for todos dentro de S // E a soma dos inteiros a 0 // Então // Saída "sim" e para

Se, e somente se, P = NP, então este é um algoritmo de tempo polinomial aceitar a linguagem NP-completa. “Aceitar” significa retornar respostas “sim” em tempo polinomial, mas é permitido executar pra sempre quando a resposta é “não”.

Este algoritmo é impraticável, mesmo se P = NP. Se o menor programa que pode resolver o SUBSET-SUM dentro do tempo polinomial é b bits de comprimento, o algoritmo acima irá tentar no mínimo 2b−1 outros programas primeiro.

Referências

• Fraenkel, A. S.; Lichtenstein, D.. Computing a Perfect Strategy for n*n Chess Requires Time Exponential in N.. doi:10.1007/3-540-10843-2+23.
• Garey, Michael (1979). Computers and Intractability. San Francisco: W.H. Freeman. ISBN [http://en.wikipedia.org/wiki/Special:BookSources/9780521122542 0716710455.
• Goldreich, Oded (2010). P, Np, and Np-Completeness. Cambridge: Cambridge University Press. ISBN 9780521122542.
• Immerman, N. (1983). Languages which capture complexity classes. pp. 347. doi:10.1145/800061.808765.
• Cormen, Thomas (2001). Introduction to Algorithms. Cambridge: MIT Press. ISBN 0262032937.
• Papadimitriou, Christos (1994). Computational Complexity. Boston: Addison-Wesley. ISBN 0201530821.
• Fortnow, L. (2009). "The status of the P versus NP problem". Communications of the ACM 52 (9): 78. doi:10.1145/1562164.1562186.