Limites Inferiores e NP-Completude

Introdução

Algoritmos são desenvolvidos com intuito de solucionar problemas encontrados no cotidiano. Como seu desenvolvimento fica restrito a imaginação de seu desenvolvedor, é comum encontrarmos uma série de algoritmos para a mesma finalidade. Resta então sabermos qual desses possui uma melhor empregabilidade no contexto analisado. Para tal, foram estipulados neste contexto, duas formas distintas para analisar a situação, conforme acrescentou Knuth(1971):

• análise de um algoritmo em particular: consiste em identificar qual custo para resolver um problema específico por um dado algoritmo, levando em conta, o número de vezes que determinada parte do código for executada, memória necessária, dentre outras.
• análise de uma classe de algoritmos: a parte que realmente nos interessa, é feita uma comparação entre todos os algoritmos apresentados para a solução, definindo assim, seus limites.

Limites

Com o objetivo de se ter uma visão mais abrangente dos algoritmos, suas respectivas complexidades e das possíveis e necessárias melhorias nos rendimentos dos algoritmos, estuda-se as limitações dos problemas propostos com relação à complexidade dos algoritmos que os resolvem.

O limite superior de complexidade de um problema refere-se ao melhor algoritmo conhecido para a resolução desse dado problema, especialmente em estudos de pior e médio casos das complexidades dos algoritmos. Já o limite inferior de um problema refere-se à melhor complexidade possível, ou seja, a identificação teórica de uma função que não permita o desenvolvimento de um algoritmo melhor que esse limite, devido principalmente às características e limites do problema proposto. A identificação desse limite inferior pode ser feita até sem o conhecimento de um algoritmo que atinja a essa complexidade, tornando assim o limite inferior distinto do limite superior.

Ao sabermos o limite inferior para uma certa situação, conseguimos verificar quanto de melhoramento podemos alcançar em um algoritmo analisado para situação apresentada. Quanto maior for a diferença entre o limite inferior e a complexidade do algoritmo apresentado, maior deverá ser a melhoria atingida.

Obtenção de limites inferiores

A forma mais simples de obter o limite inferior de um dado problema é baseado na contagem do número de itens que devem ser processados e o número de saídas que serão resultadas. Como basicamente toda resolução de um problema necessita da contagem dos elementos de entrada e saída, chegamos assim ao limite inferior trivial.

Outro meio importante de estabelecer o limite inferior é verificar a quantidade de iterações que devem ser executada. Podemos considerar a necessidade de encontrar um determinado elemento em um conjunto de 1 a n termos, realizando perguntas básicas sucessivas para obtenção de caminhos a serem perseguidos. Essa situação nos leva a percorrer ao menos log₂ n os caminhos apresentados. Tal situação é conhecida como limites inferiores teoria-informação, bastante utilizado em problemas que envolvem ordenação e pesquisa.

Esta situação pode ser melhor explicada através do mecanismo de árvore de decisão.

Árvores de decisão

Diversos algoritmos, especialmente os de busca e ordenação, trabalham realizando a comparação de seus itens de entrada e de acordo com o resultado obtido ocasiona caminhos distintos a serem seguidos.

Figura 1. Árvore de decisão

Cada nó referenciado em uma árvore representa uma comparação entre elementos e as folhas obtidas através das comparações são os resultados. Sendo que, o número de folhas deve ser pelo menos igual ao número de resultados possíveis.

A complexidade de uma algoritmo pode ser estabelecido através do percurso entre a raiz e uma folha. O pior caso alcançado por essa situação é quando o número de comparações atinge a altura da árvore, 2^h. Temos:

h >= log₂ n.
Onde,
h = altura da árvore
n = folhas.

Problemas

Um problema pode ser entendido como uma questão que deve ser respondida por uma situação específica. Para determinar sua solução é preciso apresentar uma descrição genérica de seus parâmetros e estabelecer quais as propriedades a resposta deve satisfazer.

Intratabilidade

Um problema é dito intratável quando o algoritmo possui uma complexidade não polinomial, i.e., possui uma complexidade, e.g., 2ⁿ, que o torna exponencial. Como a solução cresce rapidamente de acordo com o tamanho de n, torna-se proibido determinar sua solução para problemas de tamanhos grandes.

Os problemas intratavéis classificam-se em: P, NP e NP-C.

Classificação de Problemas

Os problemas classificados como P, são problemas que podem ser resolvidos com um tempo polinomial determinísticos. Esta classe é chamada de polinomial.

Um problema é determinístico quando se consegue sua solução exata a cada passo.

Entretanto, existem uma série de problemas que não foram descobertos o tempo polinomial e nem foi provada a existência de algum algoritmo que os soluciona. Estes problemas tem em comum um crescimento exponencial em relação ao tamanho de entrada. No entanto, dependendo do tamanho de entrada que teremos para um determinado problema, podemos estabelecer uma solução correta em tempo polinomial, tais problemas são conhecidos como problemas NP. Qualquer problema P está em NP.

Isto leva a questão teórica aberta mais importante da ciência da computação:

P = NP ou P ≠ NP?

Muitos cientistas falharam em provar tais afirmações.

Um problema que está contido em NP e pode ser reduzido a um tempo polinomial é conhecido como problema NP-Completo, i.e, um problema de decisão D1, é dito polinomialmente redutível a um problema D2, se existe um função de tempo t, que transforme as instâncias D1 em instâncias D2.

Tal descrição implica que se um problema D1 é redutível a D2, e D2 pode ser resolvido em um tempo polinomial, logo D1 é resolvido em tempo polinomial. Um problema é dito NP-Completo se: pertence a NP e todo problema NP é redutível D.

Figura 2. Abrangência de problemas

Exemplo de problema – Torre de Hanoi

A Torre de Hanoi é um quebra-cabeça que se caracteriza por uma base contendo três pinos, e em um dos quais são dispostos discos um sobre o outro, obedecendo a ordem de diâmetro, nunca podendo ficar um elemento de maior diâmetro sobre um elemento de menor diâmetro. O problema consiste em passar todos os discos colocados em um pino, para qualquer um outro pino, movendo um disco por vez e não violando a ordem de diâmetro.

Para solucionarmos o problema envolvido na Torre de Hanoi, executa-se no mínimo 2ⁿ-1 movimentos para transferir os discos do primeiro pino para o local de destino.

Tabela 1. Amostra de movimento empregados para solução da Torre de Hanoi

A solução do problema é naturalmente recursivo e pode ser resolvido percorrendo os seguintes passos:

1. a única operação possível de ser executar é mover o disco de um pino para o outro.
2. deve-se transferir o disco do pino de origem para um pino auxiliar.
3. deve-se transferir o disco do pino de origem n - 1 para um pino de destino.
4. transferir a torre formada no pino auxiliar para a torre de destino.

Tais passos devem ser repetidos até conseguirmos resolver o problema proposto.

Figura 3. Torre de Hanoi

Exemplo básico em pseudo-linguagem(portugol).

módulo tranferencia(tamanho, origem, destino, auxiliar)

se tamanho=1

então move disco da origem para o destino
senão início

transferencia(tamanho-1, origem, auxiliar, destino)
transferencia (N-1, auxiliar, destino, origem)

fim

Referências

TOSCANI, Laira Vieira. VELOSO, Paulo A. S.. Complexidade de Algoritmos: Complexidade do Problema. Porto Alegre: 1. ed. Sagra Luzzato, 2001. P. 171-195.

ZIVIANI, Nivio. Projto de Algoritmos: Com implementação em C e Pascal. São Paulo: 5. ed. Pioneira, 2000.

WIKIPEDIA. Torre de Hanoi. Disponível em: <http://pt.wikipedia.org/wiki/Torre_de_Hanoi>. Acesso em 23 nov. 2008.

José Mauro da Silva Sandy

---

Leia Também -

• Funções Anônimas - Funções Anônimas em Python: Lambda
• Fábrica de Software - Detalhes sobre a criação correta de um software