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.

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:

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):

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:

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.

Exercícios 1

  1. Mostre como um algoritmo para o problema do máximo divisor comum poderia ser usado para resolver o problema do divisor comum grande.  Mostre como um algoritmo para o problema do divisor comum grande poderia ser usado para resolver o problema Divisor-Comum-Grande.
  2. ★ Mostre como um algoritmo para o problema da subsequência crescente máxima poderia ser usado para resolver o problema da subsequência crescente longa.  Mostre como um algoritmo para o problema da subsequência crescente longa poderia ser usado para resolver o problema Subseq-Cresc-Longa.
  3. ★ Mostre como um algoritmo para o problema do conjunto independente máximo poderia ser usado para resolver o problema do conjunto independente grande.  Mostre como um algoritmo para o problema do conjunto independente grande poderia ser usado para resolver o problema Independente-Grande.

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 é

Ο(Ni) ,

sendo N o tamanho de uma instância. É polinomial, por exemplo, todo algoritmo que consome no máximo 100 N 4 + 300 N 2 + 5000 unidades de tempo. Também é polinomial todo algoritmo que consome no máximo 200 N 9 log N unidades de tempo, pois 200 N 9 log N < 200 N 10.

Algoritmos polinomiais são considerados razoavelmente rápidos, embora seja difícil aceitar como rápido um algoritmo que consome tempo proporcional a N 50, 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.

Exemplo A.  O algoritmo SSC-Max-PD para o problema da Subsequência crescente máxima é polinomial.  Já o algoritmo Subset-Sum-Prog-Din para o problema Subset-sum não é polinomial.

Algoritmos não polinomiais — como, por exemplo, os que consomem tempo proporcional a 2N ou proporcional a 1.1N — 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 2N, 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 Θ(Nic), 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.)

Exercícios 2

  1. Descreva algoritmos polinomiais para cada um dos seguintes problemas:  quadrado perfeito, equação inteira do segundo grau, máximo divisor comum, subsequência crescente máxima e caminho mínimo.
  2. Descreva informalmente um algoritmo (não necessariamente polinomial) que resolva o problema da fatoração.
  3. Descreva informalmente um algoritmo (não necessariamente polinomial) que resolva o problema do conjunto independente grande.
  4. Descreva informalmente um algoritmo (não necessariamente polinomial) que resolva o problema do circuito hamiltoniano.
  5. Suponha que as instâncias de um certo problema são pares de cadeias de caracteres. O tamanho de uma instância é então da forma  N+M, onde N é o comprimento da primeira cadeia do par e M é o comprimento da segunda cadeia. Suponha que tenho um algoritmo para o problema que consome Ω(N 2M) unidades de tempo. Mostre que o algoritmo não é polinomial.
  6. Suponha que cada instância de um certo problema consiste em um número natural k, um número natural n e um vetor x1, … , xn cujos componentes são elementos do conjunto {1, 2, 3}. Suponha que um algoritmo resolve qualquer instância do problema em Ο(kn² log n) unidades de tempo. Esse algoritmo é polinomial?

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.)

Exercícios 3

  1. Discuta a seguinte afirmação:  Se X é um problema não polinomial então todas as instâncias de X são difíceis (ou seja, não podem ser resolvidas em tempo polinomial).
  2. Mostre que os seguintes problemas estão na classe P:  Quadrado-Perfeito, Eq-Grau-2, Divisor-Comum-Grande, Subseq-Cresc-Longa e Caminho-Curto.
  3. O problema Caminho-Simples-Longo está na classe P?
  4. O problema da subsequência crescente longa está na classe P? O problema da subsequência crescente máxima está na classe P?

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:

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.

Exercícios 4

  1. Mostre que cada um dos seguintes problemas de decisão está na classe NP:  Divisor-Comum-Grande, Subseq-Cresc-Longa, Subset-Sum, Mochila-Boa, Caminho-Curto, Caminho-Simples-Longo, Circuito-Simples-Longo, Independente-Grande, Cobertura-Pequena, Campo-Minado.

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, PNP, 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 YX, se Y for um subproblema, ou caso particular, de X.  Eis alguns exemplos simples:

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 YX, 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 YX 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.

Exercícios 5

  1. Mostre que o problema Quadrado-Perfeito é polinomialmente redutível ao problema Eq-Grau-2. Reciprocamente, mostre que o segundo problema é polinomialmente redutível ao primeiro.
  2. Mostre que o problema Circuito-Hamiltoniano é polinomialmente redutível ao problema Circuito-Simples-Longo. Mostre a recíproca.
  3. Set partition. Suponha que p1, … , pn são números naturais e seja N o conjunto {1, … , n}. Para qualquer subconjunto I de N, seja p(I) a soma ∑ (pi : iI). Dizemos que uma divisão equilibrada de N é um par ( J, K) de conjuntos tal que JK = N, JK = ∅, e p(J) = p(K). (Como J ou K podem ser vazios, não posso dizer que ( J, K) é uma partição de N.)  O problema Set-Partition consiste no seguinte: dados p1, … , pn, decidir se existe uma divisão equilibrada de {1, … , n}.  Mostre que Set-Partition ≼ Subset-Sum. Em seguida, mostre que Subset-Sum ≼ Set-Partition.
  4. Mostre que Mochila-Boa ≼ Subset-Sum.
  5. Mostre que Cobertura-Pequena ≼ Subset-Sum.
  6. Mostre que todo problema da classe P é polinomialmente redutível ao problema Circuito-Hamiltoniano.
  7. Suponha que os algoritmos A e B transformam cadeias de caracteres em outras cadeias de caracteres. Suponha que A consome Ο(N 2) unidades de tempo e B consome Ο(N 4) unidades de tempo, sendo N é o número de caracteres da cadeia de entrada. Considere agora o algoritmo AB que consiste na composição de AB, com B recebendo como entrada a saída de A. Qual o consumo de tempo de AB?
  8. Seja X um problema de decisão que tem pelo menos uma instância sim e pelo menos uma instância não. Seja Y um problema da classe P. Mostre que YX.

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íveisX, isto é, se XY 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 XZ então Z também é NP-completo.  O conjunto dos problemas NP-completos será designada por NPC.

Os seguintes problemas são NP-completosSubset-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 = ∅.

Exercícios 6

  1. Suponha que X é um problema NP-completo. É verdade que todas as instâncias de X são difíceis?
  2. ★ Sabendo-se que o problema Subset-Sum é NP-completo, mostre que o problema Set-Partition é NP-completo.
  3. Mostre que o problema do Campo-Minado é NP-completo. [Solução: veja artigo de Ian Steward no sítio do Clay Mathematics Institute.]
  4. Suponha que P ≠ NP. Quais das seguintes afirmações podemos inferir a respeito de um problema de decisão X?  (a) Se X é NP-completo então X não pode ser resolvido em tempo polinomial. (b) Se X está em NP então X não pode ser resolvido em tempo polinomial. (c) Se X está em NP mas não é NP-completo então X pode ser resolvido em tempo polinomial. (d) Se X está em P então X não é NP-completo.
  5. O seguinte post apareceu em um blog:  De forma bem resumida: Existem dois tipos de problemas: os triviais e os não triviais. Os problemas triviais são facilmente resolvidos, com operações matemáticas simples. Já os problemas não triviais só podem ser resolvidos com algoritmos. E é aí que mora o perigo. Existem os problemas não-triviais tratáveis. Esses problemas tem algoritmos do tipo polinomial (lembra da quinta série?). Aí é tranquilo. Qualquer Pentium 100 consegue liquidar em segundos. Esses algoritmos são tidos como de classe P. Alguns problemas não triviais não tem algoritmos de resolução conhecidos pelo homem. São chamados indecidíveis. Esses aí, a humanidade ainda vai levar alguns séculos pra resolver. Mas existem problemas intratáveis. São esses o xis da questão. Eles tem algoritmos conhecidos, mas os algoritmos não são polinomiais. Por isto, alguns deles são tão complexos que nosso poder computacional atual não consegue resolvê-los. Esses algoritmos são tidos como de classe NP. São esses problemas que demandam super-computadores e que levam horas, dias, anos, séculos para serem resolvidos por uma máquina. Por isso, os matemáticos estão sempre quebrando a cabeça pra transformar os algoritmos não-polinomiais em polinomiais. E eles tem tido sucesso em vários deles. Até que um dia alguém perguntou: peraí! Será que eu consigo transformar QUALQUER algoritmo não-polinomial e um algoritmo polinomial? Em boa matemática: será que P=NP? Se for, qualquer problema intratável passa a ser tratável.  Discuta o post detalhadamente.

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:

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:

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).

Exercícios 7

  1. Enuncie os complementos de todos os problemas de decisão da lista dada no início da página.
  2. O problema co-Caminho-Curto é polinomialmente verificável? Em outras palavras, o problema Caminho-Curto pertence à classe co-NP?
  3. Considere o problema de decidir se um número natural é primo. Esse problema está na classe NP? Está na classe co-NP?
  4. Certificado para co-Independente-Grande?  Considere o problema de decisão Independente-Grande.  Prove que uma instância (G, k) do problema tem solução não se e somente se G tem uma cobertura mínima com mais que n − k vértices.  Essa prova coloca o problema Independente-Grande na classe co-NP?
  5. ★ Mostre que todo problema de decisão da classe P está na classe co-NP (ou seja, que P ⊆ co-NP).
  6. ★ É verdade que o complemento de todo problema da classe P também está na class P?
  7. É verdade que NP ⊆ co-NP? É verdade que NP ⊇ co-NP?