Designer

-------------------------------------------------
Análise de Algoritmos – Classes de Complexidade

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 tal algoritmo não existe.

São problemas que a complexidade por ser O(N k )

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 vértices de N’ não é adjacente.

Dados: Um grafo G e um inteiro k > 0.
Decisão: G possui um conjunto independente de vértices de tamanho > k ?

Classe NP de Problemas

Um problema não deterministicamente polinomial é um problema computável cujas soluções até então conhecidas são de ordem exponencial e não se sabe se existe uma solução melhor, de complexidade polinomial.

Observe que o termo "não-determinístico" não implica aleatoridade, mas apenas não se pode afirmar a existência de um algoritmo de complexidade polinomial para o problema em consideração.
Outra observação interessante é que a comprovação de uma solução correta de um problema NP tem complexidade da ordem polinomial,ou seja, a classe NP consiste nos problemas que são verificáveis em tempo polinomial.
Um computador não-determinístico é uma máquina hipotética.
# infinito de processadores a funcionar em paralelo.
Se a verificação de uma solução