MO417 - Ata da Aula

NP completude I

1. Introdução
2. Problemas NP-completos
2.1. Visão Geral
2.2. Pares de Problemas
2.3. Importância da teoria NP completo
2.4. Problemas de Decisão x Otimização
2.5. Aplicação do adjetivo "NP completo"
2.6. Problemas, codificações e linguagens
3. Conclusões
4. Referências bibliográficas

1. Introdução

Uma breve descrição dos tópicos do capítulo 34 do livro do Cormen (2002) será apresentada nesta ata. Todos os tópicos aqui apresentados foram abordados durante a aula da disciplina Complexidade de Algoritmos ministrada no 1º semestre letivo de 2003 pelo professor João Meidanis, na data do dia 13 de junho de 2003, das 08:00 às 10:00.



2. Problemas NP-completos

2.1. Visão Geral (Ricardo)

          A maioria dos algoritmos estudados até aqui possue complexidade de ordem polinomial sobre o tamanho da entrada, i.e., para uma entrada de tamanho n, seu tempo de execução no pior caso é O(n^k), para alguma constante k. É natural imaginarmos que todos os problemas podem ser resolvidos em tempo polinomial. Pelo contrário, existem problemas que nem mesmo podem ser resolvidos por um computador, não importando o seu tempo de execução, tal como o Turing halting problem (ou problema de parada de Turing). Outros problemas que podem ser resolvidos não podem encontrar a solução em tempo polinomial, levando tempo superpolinomial (qualquer função com crescimento superior a um polinômio). Tais problemas são considerados como sendo intratáveis ou difíceis. Já os problemas que podem encontrar a solução em tempo polinomial são considerados como sendo tratáveis.
          Iremos tratar aqui da classe de problemas chamados NP-completos, cujo status é desconhecido. Qualquer problema da classe NP-completo não possui ainda nenhum algoritmo de tempo polinomial já descoberto capaz de solucioná-lo; nem mesmo ninguém ainda foi capaz de provar que não pode existir nenhum algoritmo de tempo polinomial para qualquer um deles. Esta questão foi um dos mais profundos e surpreendentes problemas de pesquisa da ciência de computação teórica desde 1971 quando foi proposto pela primeira vez.




2.2. Pares de Problemas (Alexandro)

          Um aspecto torturante dos problemas NP-completos é que vários deles parecem a princípio serem semelhantes a outros problemas que têm algoritmos de tempo polinomial. Citaremos a seguir alguns pares de problemas onde, apenas um deles, pode ser resolvido em tempo polinomial, enquanto que o outro é NP-completo, e a diferença entre eles pare ser muito pequena.

• Caminhos simples mais curtos e mais longos de um grafo:
       Encontrar em um grafo caminhos simples mais curtos já foi discutido nas atas dos dias 21/05/2003 e 21/05/2003, onde é possível encontrar caminhos simples mais curtos a partir de uma única origem em um grafo orientado G(V,E) no tempo O(VE). Porém, encontrar o caminho simples mais longo entre dois vértices é NP-completo, até mesmo se todos os pesos das arestas forem iguais a 1.
• Ciclo Euleriano e ciclo hamiltoniano:
       Um ciclo euleriano de um grafo orientado conexo G(V,E) é um ciclo que percorre cada aresta de G exatamente uma vez, embora possa visitar um vértice mais de uma vez. Isso pode ser determinado em tempo O(E). Um ciclo hamiltoniano de um grafo orientado G(V,E) é um ciclo simples que contém cada vértice em V. Determinar se um grafo orientado conexo tem um ciclo hamiltoniano é NP-completo, mesmo se o grafo for não orientado. O Ciclo Euleriano é fácil porque basta verificar se todo vértice tem grau par, porque você tem que entrar e sair. Isso é uma condição necessária que provou-se ser suficiente também.
• Satisfabilidade 2-CNF e satisfabilidade 3-CNF:
       As variáveis de uma fórmula booleana podem ter os valores 0 ou 1, e são relacionadas pelos operadores conectivos /\ (AND), \/ (OR), e ¬ (NOT); e parênteses. Se uma fórmula booleana é satisfazível, então existe uma combinação de atribuições para as suas variáveis tal que o resultado de sua avaliação seja 1. Uma fórmula booleana está em k-CNF (forma normal k-conjuntiva) se as cláusulas AND têm cláusulas OR de exatamente k variáveis ou suas negações. A fórmula booleana abaixo está em 2-CNF:
  (x₁ \/ ¬x₂) /\ (¬x₁ \/ ¬x₃) /\ (¬x₂ \/ ¬x₃) Esta fórmula é satisfazível se as atribuições x₁ = 1, x₂ = 0 e x₃ = 1 forem utilizadas. Existe um algoritmo de tempo polinomial para determinar se uma fórmula de 2-CNF é satisfazível, porém, determinar se uma fórmula de 3-CNF é satisfazível é NP-completo. Observe que você pode construir uma fórmula tanto com OR quanto com AND, mas quando o OR está do lado de fora dos parênteses, e o AND dentro, é trivial. Você avalia separadamente cada parênteses. O primeiro que satisfizer, você resolveu o problema. Com o AND do lado de fora dos parênteses é mais complicado.
  

Temos ainda o problema da parada (Turing halting problem), considerado impossível de ser resolvido computacionalmente. Ele consiste no seguinte problema: Dado um programa, você quer saber se este programa, para alguma entrada, ele entra em loop infinito ou nunca entra em loop. Seria interessante ter um programa que avaliasse se outro programa entra em loop ou não. Só que esse programa foi provado e confirmado que é impossível de ter um programa que faça isso. Então temos o fácil: polinomial, difícil: NP-completo, e impossível: problema da parada.



2.3. Importância da Teoria NP completo (Ivan)

           A classe P consiste na classe de problemas que podem ser resolvidos em tempo polinomial, i.e., podem ser resolvidos no tempo O(n^k) para alguma constante k, onde n é o tamanho da entrada do problema. A maioria dos problemas estudados até aqui é da classe P.
           Já a classe NP consiste nos problemas que são verificáveis em tempo polinomial. Informalmente, dizemos que um problema está na classe NPC (NP-completo) se ele está em NP e é tão "difícil" quando qualquer problema NP. E se qualquer problema NP-completo puder ser resolvido em tempo polinomial, então todo problema NP-completo tem um algoritmo polinomial. Não podemos eliminar o fato de que os problemas NP-completos possam de fato ser resolvidos em tempo polinomial porém, até hoje, nenhum algoritmo de tempo polinomial foi encontrado e nenhuma prova existe de que tais algoritmos não existem.
           É importante conhecer os rudimentos dessa teoria para que se possa identificar um problema como NP-completo. Dessa forma, você terá uma boa evidência da intratabilidade do mesmo. Seu tempo será melhor se você desenvolver um algoritmo de aproximação ou resolvendo um caso especial tratável, ao invés de procurar por um algoritmo rápido que resolva o problema exatamente. Outra forma de se tentar resolver o problema, além da utilização de algoritmos de aproximação e da restrição da entrada do problema, é utilizar o método "força bruta", onde você testa todas as possibilidades, e você sabe que ele vai funcionar para até um certo tamanho, para o qual você consegue esperar. Passou daquele tamanho, você não consegue mais. Podemos utilizar este método porque se consegue verificar o resultado em tempo polinomial. Posteriormente será estudado sobre verificação de problemas, e veremos que em geral é mais fácil verificar um solução do que calcular as soluções para um determinado problema.



2.4. Problemas de decisão x problemas de otimização (Fábio)

           Muitos problemas de interesse são problemas de otimização. Estes problemas são aqueles que têm um valor associado a cada solução possível, e deseja-se encontrar a solução possível com o melhor valor. Para exemplificar, no problema SHORTEST-PATH de se encontrar o menor caminho entre dois vértices u e v de um grafo, desejamos encontrar o caminho de u até v que utiliza o menor número de arestas (para um gafo não-ponderado). Porém, o caráter NP-completo não se aplica a problemas de otimização, mas problemas de decisão, em que a resposta é simplesmente SIM ou NÃO, ou de um modo mais formal, 0 ou 1. Só que existe um relacionamento entre problemas de decisão e de otimização.
           De uma maneira geral, podemos transformar um problema de otimização em um problema de decisão, utilizando um limite para o valor associado ao problema. Por exemplo, digamos que um problema de decisão PATH nos retorna se existe um caminho de u a v consistindo em no máximo k arestas, para um grafo orientado não ponderado G(V,E). O problema de decisão SHORTEST-PATH poderia então utilizar PATH várias vezes, alterando o limite k até encontrar o valor k que representa o menor caminho entre os dois vértices dados. Este relacionamento entre problemas de decisão e problemas de otimização é importante quando tentamos provar que um problema de otimização é "difícil", visto que um problema de decisão é geralmente mais "fácil" que um problema de otimização, ou em outras palavras, é pelo menos "não mais difícil".

2.5. Aplicativo do adjetivo "NP-completo" (José Augusto)

          Queremos agora nos preocupar em mostrar que um problema não é mais difícil ou mais fácil que outro, até mesmo quando ambos os problemas são problemas de decisão. Considere um problema de decisão A qualquer, e digamos que gostaríamos de resolvê-lo em tempo polinomial. Definimos uma instância de um problema como sendo uma entrada para este problema. Vamos supor ainda que existe um outro problema B, diferente e também de decisão, e que já sabemos como resolvê-lo em tempo polinomial. Então, se tivermos um algoritmo de redução que transforme qualquer instância do problema A em alguma instância do problema B, levando essa transformação tempo polinomial, e para cada instância SIM de A, a resposta de B também seja SIM, e para cada instância NÃO de A, a resposta de B também seja NÃO, então esse algoritmo de redução pode ser utilizado para resolver o problema A em tempo polinomial. Como cada uma das etapas demora tempo polinomial, então o tempo total para resolver A é polinomial. Reduções são muito importantes para o caráter NP-completo, pois na prática, queremos mostrar o quanto um problema é difícil, em vez de mostrar o quanto ele é fácil. Para isso, usamos reduções de tempo polinomial de maneira oposta mostrando que um problema é NP-completo. Isso nos permite dizer que, quando um problema A é NP-completo e é redutível em tempo polinomial a um outro problema B, dizemos que B também é NP-completo, já que se e resolver B em tempo polinomial, então eu resolvo A também.
          A experiência mostrou que, uma vez que é descoberto um algoritmo de tempo polinomial para um problema, outros algoritmos mais eficientes vão surgindo com o decorrer do tempo. Portanto, mesmo que um algoritmo tenha tempo de execução O(n¹⁰⁰), ele ainda pode ser considerado como tratável, e sabemos que na prática existem poucos problemas que exigem tempo na ordem de um polinômio de tão alto grau.

2.6. Problemas (Camila), codificações (André) e linguagens (Eduardo)

           Definimos um problema abstrato Q como uma relação binária sobre um conjunto I de instâncias de problemas e um conjunto S de soluções de problemas. Em nosso caso, podemos ver um problema de decisão abstrato como uma função que mapeia o conjuntos de instâncias I para o conjunto solução {0,1}. Como vimos anteriormente, os problemas abstratos de otimização com seu valor associado podem ser associados a problemas abstratos de decisão, não mais difícil que o anterior.
           Muitas vezes, temos a dúvida entre fazer uma função para mapear algo ou utilizar uma tabela para este mapeamento. A vantagem de se utilizar uma função é que se usa pouco espaço, e de se utilizar tabela é que o acesso é imediato. A desvantagem de se utilizar uma função é que demora mais, e de se utilizar tabela é a quantidade de espaço necessário pode ser muito grande (embora finito). Um problema abstrato pode então ser considerado como uma tabela onde se tem as soluções. Claro que essa tabela não é factível ter se ter na memória.
           Se um programa de computador deve resolver um problema abstrato, devemos então utilizar uma codificação de um conjunto S de objetos abstratos que realiza um mapeamento e de S para um conjunto de cadeias binárias. Dessa forma, a codificação e(17) = 10001 seria o mapeamento do número natural 7 para sua representação binária 10001. Na realidade, quando dizemos que um algoritmo de computador resolve um problema de decisão abstrato, estamos dizendo que ele toma uma codificação de uma instância de problema como entrada. Definimos um problema concreto como sendo um problema cujo conjunto de instâncias é um conjunto de cadeias binárias. Um algoritmo resolve um problema concreto no tempo O(T(n)) se, quando fornecida uma instância i do problema com comprimento n = | i |, o algoritmo pode produzir a solução no tempo máximo O(T(n)). Agora podemos definir a classe de complexidade P como o conjunto de problemas de decisão concretos que podem ser resolvidos em tempo polinomial, i.e., em tempo O(n^k), para um k qualquer. Dizemos que dois problemas são polinomialmente relacionados se existir um algoritmo polinomial que possa calcular a codificação de um problema a partir da codificação do outro, e vice e versa. É bom esclarecer que a codificação não influencia no fato do problema poder ou não ser resolvido em tempo polinomial.
           Vamos agora definir um alfabeto S como sendo um conjunto finito de símbolos. Agora podemos definir uma linguagem L como sendo qualquer conjunto de cadeias formadas por símbolos do alfabeto S. Para exemplificar, seja S = {0,1}, então podemos definir a linguagem L = {10,11,101,111,1011,1101,10001,...} como sendo a linguagem de representação dos números primos. Essa definição é importante para podermos utilizar toda a teoria de conjuntos como suporte para a interpretação dos problemas. Podemos definir informalmente uma classe de complexidade como um conjunto de linguagens, cuja pertinência é determinada por uma medida de complexidade, tal como o tempo de execução, de um algoritmo que determina se uma dada cadeia x pertence à linguagem L.

3. Conclusões

De uma forma geral, abordamos as principais definições iniciais sobre os problemas NP-completos. Todos os conceitos relacionados aqui são extremamente importantes para o entendimento da teoria sobre NP-completude. A necessidade de se compreender as características desses problemas, os relacionamentos entre eles, e as técnicas utilizadas para a definição formal do tipo de problema são muito importantes para que, na prática, não se tente resolver um problema aparentemente parecido com outros problemas que são facilmente solucionáveis, mas que no fundo oferecem uma dificuldade muito superior e acabam por inviabilizar qualquer implementação que tente encontrar a solução exata. O restante da teoria será tratado na próxima ata de aula.

4. Referências bibliográficas

(Cormen, 2002) Cormen, T.H.;Leiserson, C.E.; Rivest, R.L.; Stein, C.; Algoritmos. Tradução da 2ª edição americana Teoria e Prática. 2002.