Análise de Algoritmos | Aulas | Dicionário | Índice

Complexidade e problemas NP-completos

Outras páginas deste sítio trataram da complexidade (consumo de tempo) de algoritmos. Esta página tratará de algo bem mais abstrato: a complexidade intrínseca de problemas.

A complexidade de um problema computacional é o consumo de tempo do melhor algoritmo possível para o problema.  É preciso lembrar que para muitos problemas o melhor algoritmo conhecido está longe de ser o melhor algoritmo possível. Podemos dizer, informalmente, que a complexidade de um problema é o tempo (como função do tamanho das instâncias) absolutamente indispensável para resolver o problema.  (Veja a página Complexidade da ordenação.)

Suponha que queremos encontrar um algoritmo razoavelmente rápido para um certo problema X. Suponha ainda que todas as tentativas de encontrar um tal algoritmo foram frustradas, embora o problema X pareça razoável. É natural, então, levantar a suspeita de que um tal algoritmo não existe. A ideia de investigar esta suspeita apenas para o problema X não parece promissora. É mais interessante estender a investigação a toda uma classe de problemas razoáveis.  Isso leva a duas perguntas fundamentais: 

1. O que é um algoritmo razoavelmente rápido?
2. O que é um problema razoável?

Para a primeira pergunta, convém adotar uma definição muito tolerante e permissiva. Já para a segunda, é apropriado adotar uma definição muito restritiva. Só depois que tivermos definições precisas para os dois conceitos, podemos tentar provar que para certos problemas razoáveis não existem algoritmos razoavelmente rápidos.

Essa investigação (que começou há 70 anos) teve grande impacto sobre a teoria e a prática da computação, embora os resultados obtidas até aqui sejam incompletos.

Esta página foi inspirada no capítulo 34 de CLRS.

Problemas computacionais

Para discutir a complexidade de problemas computacionais, precisamos de um repertório de exemplos. Listamos a seguir exemplos de três diferentes tipos.

Problemas de otimização.  Começamos com problemas de otimização (= optimization), ou seja, problemas que pedem o mínimo ou o máximo de alguma coisa. Vários dos problemas da seguinte lista já foram estudados em outras páginas deste sítio:

• Máximo divisor comum:  Encontrar o maior divisor comum de dois números inteiros positivos m e n.
• Subsequência crescente máxima:  Encontrar uma subsequência crescente máxima de uma sequência s₁, … , s_n de números naturais.
• Mochila ótima:  Dados números naturais p₁, … , p_n, v₁, … , v_n e c, encontrar um subconjunto K de {1, … , n} tal que a soma ∑ (p_k : k ∈ K) não passe de c e a soma ∑ (v_k : k ∈ K) seja máxima.
• Árvore geradora mínima:  Dado um grafo com pesos nas arestas, encontrar uma árvore geradora do grafo que tenha peso mínimo (ou constatar que o grafo não tem árvore geradora).
• Caminho mínimo:  Dados vértices r e s de um digrafo, encontrar um caminho de comprimento mínimo de r a s no grafo (ou constatar que não há caminho algum de r a s).
• Caminho simples máximo:  Dados vértices r e s de um grafo, encontrar um caminho simples de r a s que tenha comprimento máximo (ou constatar que não há caminho algum de r a s).
• Circuito simples máximo:  Encontrar um circuito simples de comprimento máximo num grafo (ou constatar que o grafo não tem circuito algum).
• Coleção disjunta máxima de intervalos:  Dada uma coleção C de intervalos na reta, encontrar uma subcoleção máxima de C que seja disjunta.
• Conjunto independente máximo:  Encontrar um conjunto independente máximo num grafo.
• Cobertura mínima:  Encontrar uma cobertura por vértices mínima num grafo.

Problemas de busca.  A lista seguinte traz exemplos de problemas que parecem mais simples pois não envolvem otimização. Cada problema pede um objeto que tenha certas propriedades. Na falta de um nome melhor, diremos que esses problemas são de busca (embora a expressão search problem seja usada por muitos livros num sentido bem mais restrito):

• Quadrado perfeito:  Dado um número natural n, encontrar um número natural x tal que x² = n (ou constatar que tal x não existe).
• Equação inteira do segundo grau:  Dados números inteiros a, b e c, encontrar um número inteiro x tal que ax² + bx + c = 0 (ou constatar que tal x não existe).
• Fatoração:  Dado um número natural n, encontrar um número natural p maior que 1 e menor que n que divida n (ou constatar que tal p não existe).
• Divisor comum grande:  Dados números naturais m, n e k, encontrar um divisor comum de m e n que seja maior ou igual a k (ou constatar que tal divisor não existe).
• Subsequência crescente longa:  Dada uma sequência s₁, … , s_n de números naturais e um número natural k, encontrar uma subsequência crescente de s₁, … , s_n que tenha comprimento maior ou igual a k (ou constatar que tal subsequência não existe).
• Subset sum:  Dados números naturais p₁, … , p_n e c, encontrar um subconjunto K de {1, … , n} tal que a soma ∑ (p_k : k ∈ K) seja igual a c (ou constatar que um tal K não existe).
• Mochila boa:  Dados números naturais p₁, … , p_n, v₁, … , v_n, c e d, encontrar um subconjunto K de {1, … , n} tal que a soma ∑ (p_k : k ∈ K) não passe de c e a soma ∑ (v_k : k ∈ K) seja maior ou igual a d (ou constatar que um tal K não existe).
• Árvore geradora leve:  Dado um grafo com pesos nas arestas e um número k, encontrar uma árvore geradora do grafo que tenha peso menor ou igual a k (ou constatar que uma tal árvore não existe).
• Caminho curto:  Dados vértices r e s de um digrafo e um número k, encontrar um caminho de r a s que tenha comprimento menor ou igual a k (ou constatar que tal caminho não existe).
• Caminho simples longo:  Dados vértices r e s de um grafo e um número k, encontrar um caminho simples de r a s que tenha comprimento maior ou igual a k (ou constatar que um tal caminho não existe).
• Circuito simples longo:  Dado um grafo e um número k, encontrar um circuito simples de comprimento maior ou igual a k (ou constatar que o grafo não tem um circuito tão longo).
• Circuito hamiltoniano:  Dado um grafo, encontrar um circuito simples que passe por todos os vértices do grafo (ou constatar que tal circuito não existe).
• Coleção disjunta grande de intervalos:  Dada uma coleção C de intervalos na reta e um número natural k, encontrar uma subcoleção de C que seja disjunta e tenha k ou mais intervalos (ou constatar que uma subcoleção tão grande não existe).
• Conjunto independente grande:  Dado um grafo G e um número natural k, encontrar um conjunto independente em G com k ou mais vértices (ou constatar que um conjunto independente tão grande não existe).
• Cobertura pequena:  Dado um grafo G e um número natural k, encontrar uma cobertura de G com k ou menos vértices (ou constatar que uma cobertura tão pequena não existe).
• Campo minado:  Dado um tabuleiro parcialmente preenchido do jogo Minesweeper, encontrar uma distribuição de minas que seja consistente com o estado do tabuleiro (ou constatar que uma tal distribuição não existe).

Há uma correspondência natural entre esses problemas de busca e os problemas de otimização listados anteriormente. Por exemplo, o problema do conjunto independente grande corresponde ao problema do conjunto independente máximo. Ademais, cada problema de busca não é mais difícil (ou é até mais fácil… ) que o correspondente problema de otimização, pois qualquer algoritmo para o segundo pode ser usado para resolver o primeiro. Por exemplo, se I é um conjunto independente máximo num grafo G, basta comparar ⎮I⎮ com k para ter uma solução da instância (G, k) do problema do conjunto independente grande (ou constatar que a instância não tem solução). Podemos indicar isso assim: (problema do conjunto independente grande) ≼ (problema do conjunto independente máximo).

É importante dar a devida atenção às instâncias dos problemas de busca que não têm solução. Essas instâncias estão diretamente relacionadas com o maximizar e o minimizar dos correspondentes problemas de otimização. Por exemplo, uma instância (G, k) do problema do conjunto independente grande não tem solução se e somente se um conjunto independente máximo da instância tem menos que k vértices.

Problemas de decisão.  Para desenvolver a teoria da complexidade, será preciso restringir a atenção a problemas ainda mais simples que os de busca, problemas cujas instâncias admitem apenas dois tipos de solução: sim e não. Diz-se que esses problemas são de decisão (= decision problem). Segue uma pequena lista de problemas de decisão:

• Quadrado-Perfeito:  Dado um número natural n, decidir se o número √n é natural, ou seja, decidir se existe um número natural x tal que x² = n.
• Eq-Grau-2:  Dados números inteiros a, b e c, decidir se existe um número inteiro x tal que ax² + bx + c = 0.
• Eq-Diofantina:  Dada uma equação polinomial com coeficientes inteiros e número arbitrário de variáveis (como x³yz + 2y⁴z² − 7xy⁴z = 6, por exemplo) decidir se existem valores inteiros das variáveis que satisfazem a equação.
• Fatoração:  Decidir se um número natural n é composto, ou seja, decidir se existe um número natural p que divide n e satisfaz as desigualdades 1 < p < n.
• Divisor-Comum-Grande:  Dados números naturais m, n e k, decidir se existe um divisor comum de m e n que seja maior ou igual a k.
• Subseq-Cresc-Longa:  Dada uma sequência s₁, … , s_n de números naturais e um número natural k, decidir se s₁, … , s_n tem uma subsequência crescente de comprimento maior ou igual a k.
• Subset-Sum:  Dados números naturais p₁, … , p_n e c, decidir se existe um subconjunto K de {1, … , n} tal que a soma ∑ (p_k : k ∈ K) seja igual a c.
• Mochila-Boa:  Dados números naturais p₁, … , p_n, v₁, … , v_n, c e d, decidir se existe um subconjunto K de {1, … , n} tal que a soma ∑ (p_k : k ∈ K) não passe de c e a soma ∑ (v_k : k ∈ K) seja maior ou igual a d.
• Árvore-Geradora-Leve:  Dado um grafo com pesos nas arestas e um número k, decidir se o grafo tem uma árvore geradora de peso menor ou igual a k.
• Árvore-Geradora-Pesada:  Dado um grafo com pesos nas arestas e um número k, decidir se o grafo tem uma árvore geradora de peso maior ou igual a k.
• Caminho-Curto:  Dados vértices r e s de um digrafo e um número k, decidir se existe um caminho de r a s que tenha comprimento menor ou igual a k.
• Caminho-Simples-Longo:  Dados vértices r e s de um grafo e um número k, decidir se existe um caminho simples de r a s que tenha comprimento maior ou igual a k.
• Circuito-Simples-Longo:  Dado um grafo e um número k, decidir se o grafo tem um circuito simples de comprimento maior ou igual a k.
• Circuito-Hamiltoniano:  Dado um grafo, decidir se o grafo tem um circuito simples que passa por todos os vértices.
• Intervalos-Disjuntos:  Dada uma coleção de intervalos na reta e um número natural k, decidir se a coleção tem uma subcoleção disjunta com k ou mais intervalos.
• Independente-Grande:  Dado um grafo e um número k, decidir se o grafo tem um conjunto independente com k ou mais vértices.
• Cobertura-Pequena:  Dado um grafo e um número k, decidir se o grafo tem uma cobertura com k ou menos vértices.
• Campo-Minado:  Dado um tabuleiro parcialmente preenchido do jogo Minesweeper, decidir se existe uma distribuição de minas que seja consistente com o estado do tabuleiro.

Há uma correspondência natural entre esses problemas de decisão e os problemas de busca vistos anteriormente. Cada problema de decisão não é mais difícil (ou é até mais fácil… ) que o correspondente problema de busca: dada uma instância do problema de decisão e a correspondente instância do problema de busca, se a segunda tem solução então a solução da primeira é sim, e se a segunda não tem solução então a solução da primeira é não. No caso dos problemas do conjunto independente, por exemplo, podemos indicar isso assim: Independente-Grande ≼ (problema do conjunto independente grande).

Estratégia.  Como os problemas de decisão não são mais difíceis que os de busca, e estes não são mais difíceis que os de otimização, é suficiente tratar dos problemas de decisão. Se provarmos que um dado problema de decisão não tem um algoritmo razoavelmente rápido, ficará demonstrado também que os correspondentes problemas de busca e de otimização não têm algoritmos razoavelmente rápidos.

Mas a classe de todos os problemas de decisão é ainda ampla demais. Será necessário restringí-la aos problemas polinomialmente verificáveis, coisa que faremos daqui a duas seções.

Algoritmos polinomiais

Dizemos que um algoritmo resolve um dado problema se, ao receber uma instância do problema, devolve uma solução da instância ou informa que a instância não tem solução. O algoritmo deve ser capaz de resolver qualquer instância do problema, mesmo aquelas que não parecem realistas e mesmo aquelas que não têm solução alguma.

Um algoritmo que resolve um dado problema é polinomial se seu consumo de tempo no pior caso é limitado por uma função polinomial do tamanho das instâncias do problema. (No caso do problema da fatoração, por exemplo, o tamanho de uma instância é o número de dígitos de n, ou seja, cerca de log n.)  Em outras palavras, o algoritmo é polinomial se existe um número i — o mesmo para todas as instâncias — tal que o consumo de tempo do algoritmo é

Ο(Nⁱ) ,

sendo N o tamanho de uma instância. É polinomial, por exemplo, todo algoritmo que consome no máximo 100 N⁴ + 300 N² + 5000 unidades de tempo. Também é polinomial todo algoritmo que consome no máximo 200 N⁹ log N unidades de tempo, pois 200 N⁹ log N < 200 N¹⁰.

Algoritmos polinomiais são considerados razoavelmente rápidos, embora seja difícil aceitar como rápido um algoritmo que consome tempo proporcional a N⁵⁰, por exemplo. Por outro lado, o conceito é ambicioso, pois o limite polinomial deve valer para todas as instâncias do problema sem exceções.  Felizmente, o expoente de N é pequeno em todos os algoritmos polinomiais de interesse prático que conhecemos.

Algoritmos não polinomiais — como, por exemplo, os que consomem tempo proporcional a 2^N ou proporcional a 1.1^N — são considerados inaceitavelmente lentos (ainda que possam ser mais rápidos que alguns algoritmos polinomiais para valores modestos de N).

Por que adotamos polinomial como definição de razoavelmente rápido?  Porque a classe dos polinômios exclui as funções exponenciais, como 2^N, e principalmente porque a classe é fechada sob as operações de adição, multiplicação e composição, o que permite combinar algoritmos polinomiais de várias maneiras sem que as combinações deixem de ser polinomiais.

(A propósito, um algoritmo é pseudopolinomial se seu consumo de tempo tem a forma Θ(Nⁱ c), sendo c o valor de algum parâmetro numérico do problema. Um bom exemplo é o algoritmo de programação dinâmica para o problema da mochila booleana. Algoritmos pseudopolinomiais não são polinomiais pois um parâmetro numérico como c contribui apenas log c para o tamanho das instâncias.)

Problemas polinomiais e a classe P

Um problema computacional é polinomial se existe um algoritmo polinomial para o problema. Problemas desse tipo são considerados tratáveis, ou fáceis. Alguns exemplos de problemas polinomiais: o problema da equação inteira do segundo grau, o problema do divisor comum grande, o problema da subsequência crescente longa, o problema do caminho curto. É claro que os correspondentes problemas de decisão também são polinomiais.

Um problema é não polinomial se não existe algoritmo polinomial que resolva o problema. (Cuidado! Não use a sigla NP como abreviatura de não polinomial!)  Não se trata de problemas para os quais não conhecemos um algoritmo polinomial hoje, mas de problemas que nunca terão um algoritmo polinomial. Problemas desse tipo são considerados intratáveis. Para resolver uma instância de um problema desse tipo, o melhor que se pode fazer é testar todos os candidatos a solução da instância.

Não é fácil dar bons exemplos de problemas não polinomiais (veja o roadblock problem). Suspeita-se que o problema do circuito hamiltoniano não é polinomial. Paira uma suspeita análoga sobre o problema da fatoração, o problema da mochila boa, e muitos outros. Mas ainda estamos longe da comprovação dessas suspeitas.

(Para além dos problemas não polinomiais, existem problemas insolúveis, também conhecidos como indecidíveis. Para esses problemas, não existe algoritmo algum que resolva o problema em tempo finito. É o caso, por exemplo, do problema das equações diofantinas, já mencionado acima.)

A classe P de problemas é o conjunto de todos os problemas de decisão que são polinomiais.  Estão na classe P os problemas Eq-Grau-2, Divisor-Comum-Grande, Subseq-Cresc-Longa, Caminho-Curto, Intervalos-Disjuntos, e muitos outros.

O problema Fatoração também está em P, como se descobriu em 2004. (Mas isso não garante um algoritmo polinomial para o correspondente problema de busca. Acredita-se que um tal algoritmo não existe.)

Problemas verificáveis e a classe NP

Podemos tratar agora da segunda pergunta fundamental no começo da página: que tipos de problemas são razoáveis?  Diremos, informalmente, que um problema é razoável se for fácil reconhecer uma solução de uma instância do problema quando se está diante de uma.

É muito fácil entender essa ideia no caso dos problemas de busca listados acima. Considere, por exemplo, o problema da equação inteira do segundo grau. É fácil verificar se um dado número x é inteiro e satisfaz a equação ax² + bx + c = 0. Para outro exemplo, considere o problema do conjunto independente grande. Dada uma instância (G, k) do problema e um conjunto S de vértices, é fácil verificar (em tempo polinomial no tamanho de G) se S é independente e tem k ou mais vértices. Algo análogo vale para cada um dos problemas de busca listados acima: é fácil conceber um algoritmo que consome tempo polinomial no tamanho das instâncias para verificar se um dado objeto é solução da instância.

Dada uma instância I de um problema de decisão X, não há como verificar a solução sim de uma instância a menos que nos seja dada alguma informação adicional, que chamaremos de certificado (ou testemunha) do sim, e esse certificado seja aceito por um verificador. Um verificador para o problema X é um algoritmo que recebe a instância I e um certificado C (do sim) e responde aceito ou rejeito. Ademais, a resposta aceito deve ocorrer em tempo limitado por uma função polinomial do tamanho de I (mas não há limite de tempo para a resposta rejeito). Uma resposta rejeito não significa que a solução da instância é não; significa apenas que o verificador não aceitou o certificado C de sim. (Uma consequência imediata é que todos os certificados aceitos são curtos, ou seja, limitados por uma função polinomial do tamanho da instância.) Para todos os problemas de decisão mencionados acima, um certificado nada mais é que uma solução do correspondente problema de busca.

Podemos, finalmente, dizer o que é um problema de decisão razoável. (Passaremos a usar a expressão técnica polinomialmente verificável em substituição à expressão informal razoável.) Um problema de decisão é polinomialmente verificável se existe um verificador para o problema que tenha a seguinte propriedade:

1. para cada instância sim, aceita algum certificado;
2. para cada instância não, não aceita nenhum certificado.

É difícil dar bons exemplos de problemas naturais que não sejam polinomialmente verificáveis. Um exemplo é o roadblock problem. Um exemplo potencial (pendente de confirmação… ) é o problema de decidir se um dado conjunto de vértices de um grafo é um conjunto independente máximo.

Todos os problemas de decisão da lista de exemplos na primeira seção desta págna são polinomialmente verificáveis. Segue a discussão de alguns daqueles exemplos:

• Eq-Grau-2:  Um certificado é um número inteiro. Um certificado x é aceito se e somente se ax² + bx + c = 0. Como o número de dígitos de uma solução x da equação não passa do número de dígitos de (a, b, c), o cálculo de ax² + bx + c consome tempo limitado por uma função polinomial do tamanho da instância do problema. Portanto, o problema é polinomialmente verificável.
• Fatoração: Um certificado é um número natural. Um certificado p é aceito se e somente se 1 < p < n e p divide n. É fácil fazer essa verificação: basta calcular n ÷ p usando o algoritmo de divisão que todos aprendemos na escola. Os cálculos consomem tempo polinomial no número de dígitos de n. Portanto, o problema da fatoração é polinomialmente verificável.
• Divisor-Comum-Grande: Um certificado é um número natural. Um certificado p é aceito se e somente se p divide tanto m quanto n e p ≥ k. Isso pode ser feito em tempo polinomial.
• Subseq-Cresc-Longa:  Um certificado é uma sequência de números naturais. Um certificado é aceito se e somente se for subsequência crescente de s₁, … , s_n e tiver k ou mais elementos. Isso pode ser feito em tempo polinomial.
• Circuito-Hamiltoniano:  Um certificado é uma sequência de vértices. Um certificado é aceito se e somente se a sequência é um circuito simples que passa por todos os vértices do grafo. Essas verificações podem ser feitas em tempo polinomial no tamanho do grafo.
• Independente-Grande:  Um certificado é um conjunto de vértices. Um certificado é aceito se e somente se o conjunto é independente e tem k ou mais vértices.

A classe NP de problemas é o conjunto dos problemas de decisão que são polinomialmente verificáveis. (Cuidado!  NP não é abreviatura de não polinomial mas sim de nondeterministic polynomial. Não vamos discutir aqui o significado do nondeterministic.)   A definição da classe NP nada diz sobre complexidade de algoritmos para o problema mas apenas sobre a existência de um verificador.

No caso de problemas da classe P, é tudo trivial. Para mostrar que o problema é polinomialmente verificável, basta usar um certificado vazio: o verificador executa um algoritmo polinomial para resolver o problema, e diz aceito se o algoritmo produzir sim e rejeito em caso contrário.

A questão P = NP?

A seção anterior estabeleceu a classe NP como o universo dos problemas razoáveis. Gostaríamos de encontrar um problema não polinomial nessa classe.

Como já observamos, P ⊆ NP, ou seja, todo problema polinomial de decisão é polinomialmente verificável. O bom-senso sugere que P é apenas uma pequena parte de NP. Surpreendentemente, ninguém encontrou ainda um problema de NP que seja não polinomial (embora existam muitos candidatos).

Esta situação abre caminho para a suspeita de que talvez P seja igual a NP. A suspeita pode ser formulada assim: É verdade que todo problema cujas soluções podem ser verificadas por um algoritmo polinomial pode também ser resolvido por um algoritmo polinomial?  A maioria dos especialistas não acredita nessa possibilidade, entretanto.

Veja o verbete P versus NP problem na Wikipedia. Veja também a página de G. Woeginger com um histórico de provas frustradas de P=NP e de P≠NP.  Veja também a resposta de Alon Amit à pergunta What is the better result of P vs. NP? Do you think the world would be better if someone released a 100% solid proof of P=NP, or would you prefer they proved P!=NP with 100% certainty? no Quora.

A propósito, o Instituto Clay de Matemática oferece um prêmio de um milhão de dólares pela solução da questão P=NP?.

Reduções e a complexidade relativa de problemas

Para cada problema da classe NP, gostaríamos de saber se o problema é fácil — isto é, polinomial — ou difícil — isto é, não polinomial. Para não enfrentar esse gigantesco desafio de frente, podemos tentar, ao menos, entender a complexidade relativa dos problemas. Trata-se de entender, para cada dois problemas em NP, se um é mais fácil ou mais difícil que o outro.

Em termos informais, podemos dizer que um problema Y não é mais difícil que um problema X, e escrever Y ≼ X, se Y for um subproblema, ou caso particular, de X.  Eis alguns exemplos simples:

• Quadrado-Perfeito ≼ Eq-Grau-2.
• Circuito-Hamiltoniano ≼ Circuito-Simples-Longo.
• Subset-Sum ≼ Mochila-Boa (veja um dos exercícios na página Mochila booleana).
• Árvore-Geradora-Pesada ≼ Árvore-Geradora-Leve (veja um dos exercícios da página Algoritmo de Kruskal para o problema MST).
• Intervalos-Disjuntos ≼ Independente-Grande (veja uma das subseções da página Conjuntos independentes em grafos).
• Cobertura-Pequena ≼ Independente-Grande (veja uma das seções da página Coberturas por vértices).

Para formalizar essa ideia, é preciso introduzir o conceito de redução polinomial. Dizemos que um problema de decisão Y é polinomialmente redutível a um problema de decisão X, e escrevemos Y ≼ X, se existe um algoritmo polinomial R que transforma qualquer instância J de Y em uma instância R(J) de X de tal forma que R(J) tem solução sim se e somente se J tem solução sim.

Os exemplos de redutibilidade polinomial dados acima são óbvios, mas há exemplos em que a redução é mais complexa. Por exemplo, o problema Cobertura-Pequena é polinomialmente redutível ao problema Circuito-Hamiltoniano.

A redução polinomial entre problemas tem a seguinte consequência: Se Y é polinomialmente redutível a X e X está na classe P então Y também está na classe P (pois a classe de todos os polinômios é fechada sob composição). Dito de outra maneira:  se Y ∉ P e Y ≼ X e então X ∉ P.  Portanto, se encontrarmos um problema de decisão não polinomial, encontraremos também imediatamente vários outros problemas não polinomiais.

Problemas NP-completos

A complexidade de muitos problemas computacionais de interesse prático é desconhecida. Para muitos desses problemas, não sabemos se um algoritmo polinomial existe. Em particular, para muitos problemas de decisão polinomialmente verificáveis não sabemos se o problema está na classe P. Resta-nos tentar entender quais desses problemas são menos provavelmente polinomiais.

Um problema X é  NP-difícil  se todos os problemas da classe NP são polinomialmente redutíveis a X, isto é, se X ≽ Y para todo Y em NP. Dito de maneira mais informal: um problema é NP-difícil se for pelo menos tão difícil quanto qualquer problema em NP. Um problema é  NP-completo  se for NP-difícil e estiver em NP.  Por volta de 1970, Steven Cook e Leonid Levin fizeram uma descoberta fundamental e surpreendente:

Teorema: Existe um problema NP-completo.

Uma vez conhecido um problema NP-completo, o conceito de redução polinomial pode ser usado para mostrar que outros problemas são NP-completos. Com efeito, se X é um problema NP-completo e X ≼ Z então Z também é NP-completo.  O conjunto dos problemas NP-completos será designada por NPC.

Os seguintes problemas são NP-completos:  Subset-Sum, Mochila-Boa, Caminho-Simples-Longo, Circuito-Simples-Longo, Circuito-Hamiltoniano, Independente-Grande, Cobertura-Pequena, Campo-Minado, e muitos outros.  Veja na Wikipedia uma lista com centenas de problemas NP-completos.

Se algum problema NP-completo for polinomial então todos os problemas NP-completos são polinomiais. Portanto, para provar que P = NP basta encontrar um algoritmo polinomial para um único problema NP-completo. Isso pode ser resumido assim: P ≠ NP se e somente se P ∩ NPC = ∅.

Apêndice: a classe co-NP

Se trocarmos os papéis de sim e não num problema de decisão, teremos um novo problema de decisão. Diremos que o novo problema é complementar ao original e usaremos o prefixo co- para dar nome ao problema. Veja três exemplos:

• co-Quadrado-Perfeito:  Dado um número natural n, decidir se o número √n não é natural, ou seja, decidir se x² ≠ n para todo número natural x.
• co-Eq-Grau-2:  Dados números inteiros a, b e c, decidir se ax² + bx + c ≠ 0 para todo número inteiro x.
• co-Fatoração:  Decidir se um dado número natural n é primo.
• co-Divisor-Comum-Grande:  Dados números naturais m, n e k, decidir se todos os divisores comuns de m e n são menores que k.
• co-Subseq-Cresc-Longa:  Dada uma sequência s₁, … , s_n de números naturais e um número natural k, decidir se toda subsequência crescente de s₁, … , s_n tem comprimento menor que k.
• co-Subset-Sum:  Dados números naturais p₁, … , p_n e c, decidir se ∑ (p_k : k ∈ K) ≠ c para todo subconjunto K de {1, … , n}.
• co-Árvore-Geradora-Leve:  Dado um grafo com pesos nas arestas e um número k, decidir se todas as árvores geradoras do grafo têm peso maior que k.
• co-Circuito-Simples-Longo:  Dado um grafo e um número k, decidir se todos os circuitos simples do grafo têm comprimento menor que k.
• co-Intervalos-Disjuntos:  Dada uma coleção de intervalos na reta e um número natural k, decidir se toda subcoleção disjunta tem menos que k intervalos.
• co-Independente-Grande:  Dado um grafo e um número k, decidir se todos os conjuntos independentes do grafo têm menos que k vértices.
• co-Campo-Minado:  Dado um tabuleiro parcialmente preenchido do jogo Minesweeper, decidir se todas as distribuição de minas são inconsistentes com o tabuleiro.

Há uma correspondência natural entre as instâncias sim dos problemas de decisão complementares e as instâncias sem solução dos problemas de busca. Por exemplo, toda instância sim do problema co-Independente-Grande — e portanto toda instância não do problema Independente-Grande — corresponde a uma instância sem solução do problema do conjunto independente grande.

Problemas de decisão complementares verificáveis.  Vários dos problemas de decisão complementares que acabamos de enunciar são polinomialmente verificáveis e têm certificados muito interessantes. Veja os certificados de alguns problemas:

• co-Quadrado-Perfeito:  Um certificado para esse problema é um número natural. Um certificado k é aceito se e somente se k² < n < (k+1)². Estas desigualdades podem ser verificadas em tempo limitado por uma função polinomial do tamanho, log n, de uma instância do problema. Se o certificado é aceito então é claro que a instância tem solução sim. Reciprocamente, se a instância tem solução sim então existe um k com a propriedade indicada. Portanto, o problema é polinomialmente verificável.
• co-Eq-Grau-2:  Um certificado para esse problema é um inteiro não negativo. Um certificado k é aceito se e somente se vale uma das seguintes condições: (1) b² − 4ac < 0, ou (2) k² < b² − 4ac < (k+1)², ou (3) k² = b² − 4ac mas nem b + k nem b − k é divisível por 2a. (No caso (1), o certificado nem é usado.)  Essas condições são verificáveis em tempo limitado por um polinômio no número de dígitos de (a, b, c). Se o certificado é aceito então é claro que a instância tem solução sim. Reciprocamente, se a instância tem solução sim então existe um k com a propriedade indicada. Portanto, o problema é polinomialmente verificável.
• co-Fatoração:  V. Pratt descobriu (1975) um certificado muito interessante, mas um tanto complexo. (Historicamente, esse foi um dos primeiros exemplos de problema de decisão polinomialmente verificável a usar um certificado não óbvio.)
• co-Divisor-Comum-Grande:  Um certificado para esse problema é um par de números inteiros. Um certificado (x, y) é aceito se e somente se 0 < xm + yn < k e xm + yn é um divisor de m e de n. Essas condições podem ser verificadas em tempo polinomial no número de dígitos de m e n. Como qualquer divisor comum de m e n é também divisor de xm + yn, concluímos que todo divisor comum de m e n é menor que k e portanto essa instância do problema tem solução sim. Reciprocamente, se uma instância do problema tem solução sim então existe um par (x, y) com as propriedades necessárias. (Veja o Concrete Mathematics, p.104. Veja Extended Euclidean algorithm na Wikipedia.)
• co-Subseq-Cresc-Longa:  Um certificado é um conjunto de subsequências. Um certificado é aceito se for uma cobertura por subsequências estritamente decrescentes e tiver menos que k subsequências. Se o certificado é aceito então é claro que a instância tem solução sim. Reciprocamente, se a instância tem solução sim então existe um certificado com a propriedade indicada conforme apêndice da página Subsequência crescente máxima.
• co-Intervalos-Disjuntos:  Um certificado é um conjunto de pontos na reta. Um certificado é aceito se for uma cobertura do conjunto de intervalos e tiver menos que k pontos. Se o certificado é aceito então é claro que a instância tem solução sim. Reciprocamente, se a instância tem solução sim então existe um certificado com a propriedade indicada conforme o apêndice da página Intervalos disjuntos.

Acredita-se que o problema co-Subset-Sum não é polinomialmente verificável, pois não foi encontrada (ainda?) uma certificado para o problema. A mesma observação vale para os problemas co-Mochila-Boa, co-Caminho-Simples-Longo, co-Circuito-Simples-Longo, co-Circuito-Hamiltoniano, co-Independente-Grande, co-Cobertura-Pequena, co-Campo-Minado, e muitos outros. Acredita-se que nenhum desses problemas é polinomialmente verificável.

A classe co-NP é o conjunto de todos os problemas de decisão cujo complemento é polinomialmente verificável. Em outras palavras, co-NP é a classe dos problemas de decisão cujas respostas não são polinomialmente verificáveis.

No caso de problemas da classe P, é tudo trivial. Para mostrar que o complemento do problema é polinomialmente verificável, basta usar um certificado vazio: o verificador executa um algoritmo polinomial para resolver o problema, e diz aceito se o algoritmo produzir sim e rejeito em caso contrário.

Não temos respostas para a maioria das perguntas interessantes. Não sabemos se P = co-NP, nem se NP = co-NP. (Mas se NP ≠ co-NP então certamente P ≠ NP.) Não sabemos se P = NP ∩ co-NP (embora conjetura pareça mais plausível que P = NP.)

Problemas de otimização verificáveis.  Para verificar um candidato a solução de uma instância de um problema de otimização, precisamos verificar se o candidato é ótimo, ou seja, se não existe candidato melhor. Essa verificação de não existência demanda algum tipo de certificado semelhante aos certificados de problemas de decisão.

Certificados polinomiais de otimalidade são bem conhecidas para alguns problemas de otimização (veja o problema da subsequência crescente máxima e o problema da coleção disjunta máxima de intervalos) mas não para outros. No caso do problema do conjunto independente máximo, por exemplo, embora seja fácil verificar se um dado conjunto de vértices é independente, não se conhece (ainda?) um certificado para verificar a maximalidade do conjunto (ou seja, um certificado que prove a inexistência de um conjunto independente maior).