Teoria da Complexidade de Algoritmos

Dizemos que um problema é tratável se o mesmo pode ser resolvido no pior caso por um algoritmo em tempo $O(n^k)$, para alguma constante $k$. E intratável caso contrário. Nesse contexto, a existência de um algoritmo que resolve um problema implica em um algoritmo que sempre retorna a solução correta para uma dada instância e, no caso de problemas de otimização, a melhor solução. Existem alguns problemas conhecidamente intratáveis, como o problema de gerar todas as permutações de um conjunto. Isso acontece porque, como uma quantidade exponencial de itens devem ser produzidos na saída, pelo menos complexidade exponencial (nesse caso, $\Omega(n!)$) qualquer algoritmo deve ter. Existem problemas para os quais, no entanto, não se sabe se são tratáveis ou intratáveis, como o problema da mochila. A teoria da complexidade busca justamente organizar o conhecimento sobre o que se sabe da complexidade de certos problemas, sendo portanto uma área com diversos questões em aberto.

Tendo em vista a definição anterior, podemos discutir a dificuldade de alguns problemas computacionais conhecidos:

• Ordenação: comprovadamente tratável, já que existem algoritmos polinomiais ($O(n^k)$ no pior caso) que o resolvem -- mergesort, selection-sort, insertion-sort, etc.
• Árvore Geradora Mínima (AGM): tratável, pelo mesmo motivo acima. Você consegue listar algoritmos famosos que resolvem esse problema em tempo polinomial?
• Permutações: gerar todas as permutações de um conjunto é um problema intratável, já que existe um limite inferior exponencial para a complexidade de um algoritmo que o resolve.
• Problema do Caixeiro Viajante (PCV): apesar de não conhecermos nenhum algoritmo polinomial que resolve o problema, não significa que não pode existir. Portanto, usando a definição acima, vamos ser conservadores e não classificar esse problema como intratável nem como tratável. De fato, essa dúvida na existência ou não de um algoritmo eficiente polinomial para um problema é o que torna o PCV (e muitos outros) tão interessantes.
• Problema da Mochila binária (PM): dúvida, pelo menos motivo do PCV.

Além disso, essa relação de tratabilidade ou dúvida aparece de maneira muito sutil em problemas relacionados. Por exemplo:

1. “Caminho mais curto” vs. “Caminho mais longo”. O primeiro é tratável, o segundo não se sabe -- só se conhece algoritmo exponencial para o segundo.
2. “Circuito hamiltoniano” vs. “Circuito euleriano”. O segundo é tratável, pela existência de uma condição suficiente e necessária para a existência de um circuito euleriano em um grafo. Você se lembra qual condição (teorema) é esta?
3. “Coloração de grafos com 2 cores” vs. “Coloração de grafos com mais de 2 cores”. O primeiro é fácil, pois é equivalente a se determinar se um grafo é bipartido. Para o segundo, não se conhece algoritmo polinomial no pior caso.

Um modelo único: problemas de decisão¶

O primeiro desafio em se categorizar problemas em classes de complexidade semelhantes vem do fato de que as definições encontradas em problemas podem ser as mais variadas, principalmente no que se refere à saída pretendida. Alguns problemas esperam como saída conjuntos de itens (Problema da Mochila, por exemplo), outros esperam permutações de itens (Problema do Caixeiro Viajante, por exemplo), outros esperam como saída grafos (Problema da Árvore Geradora Mínima, por exemplo). Por isso, iremos considerar no nosso estudo um tipo específico de problema, aquele que espera como saída apenas sim ou não, conhecidos como problemas de decisão. É razoável considerar apenas problemas de decisão porque sempre podemos formular um problema qualquer como uma sequência de soluções de problemas de decisão. Por exemplo, considere o problema da Coloração Mínima: dado um grafo, encontrar a quantidade mínima de cores a serem atribuídas aos vértices de tal forma que nenhum par de vértices adjacentes compartilhe a mesma cor. Pois bem, as seguintes perguntas do tipo sim ou não nos ajudariam a resolver o problema:

1. Existe coloração válida com k = 1 cor?
2. Existe coloração válida com k = 2 cores?
3. Etc.

Perceba que na primeira pergunta para qual a resposta seja sim, teríamos a solução para o problema de otimização que busca a coloração mínima. Essa mesma lógica pode ser aplicada a diversos problemas de propósito geral. Dessa forma, a partir de agora iremos considerar categorizar apenas problemas de decisão, já que sempre temos uma versão de decisão de um problema que nos ajuda a resolver o original.