Complexidade de Algoritmos - Problema P versus NP

1. Introdução

A Complexidade Computacional é um ramo da Matemática Computacional que estuda a eficiência dos algoritmos. Do ponto de vista prático, de nada adianta um algoritmo perfeito se sua implementação computacional demora uma centena de anos para ser processada. Mesmo tarefas relativamente simples, como o produto de dois números com muitos dígitos, pode demorar alguns minutos para serem concluídas em alguns computadores. Se considerarmos que alguns algoritmos necessitam multiplicar números muito grandes milhares de vezes esses alguns minutos podem se transformar em um tempo excessivamente longo. Para medir a eficiência de um algoritmo freqüentemente usamos o tempo teórico que o programa leva para encontrar uma resposta em função dos dados de entrada. Este cálculo é feito associando-se uma unidade de tempo para cada operação básica que o procedimento executa. Se a dependência do tempo com relação aos dados de entrada for polinomial, o programa é considerado rápido. Se, entretanto, a dependência do tempo for exponencial o programa é considerado lento.

2. Classe P de problemas

A classe P de problemas é o conjunto de todos os problemas polinomiais, ou seja, o conjunto de problemas que têm complexidade O( N k ) para algum k. Para muitos problemas não sabemos (ainda) se ele está ou não em P, pois ainda não descobrimos um algoritmo polinomial nem conseguimos demonstrar que um tal algoritmo não existe.

Exemplos: Alguns Problemas para os quais, até o momento, não se conhece a existência de algoritmos polinomiais.

Problema: Coloração

Definição: Uma coloração de um grafo G = (N, M) é uma atribuição de cores aos vértices de G, tal que vértices adjacentes têm cores diferentes.

Dados: Um grafo G e um inteiro K > 0.

Decisão: G possui uma coloração com um número < k de cores ?

Problema: Conjunto Independente de Vértices.

Definição: Dado um grafo G = (N, M) um conjunto independente de vértices

é um subconjunto N’ ? N tal que todo par de