Problemas P, NP e NP-Completo
Problemas que no pior caso estão em O(p(n)) sendo p(n) um polinômio de de uma entrada de tamanho n
Classe P
Classe NP
Classe NP-Completo
Problemas polinomiais são ditos tratáveis
Problemas não polinomiais são ditos intratáveis
Problemas polinomiais
Problemas de decisão cuja resposta são sim u não
Problemas de decisão que algorítimos não podem resolver
Problemas de decisão que algorítimos podem resolver
Resolver alguns problemas possa ser computacionalmente difícil, verificar se uma solução proposta realmente resolve o problema pode ser computacionalmente fácil, ou seja, pode ser feito em tempo polinomial.
Algoritimo não determinístico
Após receber uma entrada
Fase determinística
Fase não determinística
Gerar arbitrariamente uma string S que pode ser um possível solução de uma instancia I do problema
Utiliza I e S como entrada se a saída for sim S é uma solução para a instância I
São capaz de adivinhar a solução de no minimo uma solução e ser capaz de verificar sua validade
Problemas de decisão não determinístico em que o a eficiência temporal da fase de verificação é polinomial
Classe P está contida na classe NP
Um problema de decisão D1 é polinomialmente redutível para D2 se existir uma função t que transforma instancias de de D1 em instâncias de D2
t mapeia todas as instâncias sim de D1 para instâncias sim de D2 e todas as instâncias não de D1 a instância não de D2
t é computável em um tempo polinomial
Pertence a classe NP
Todos problema em NP é polinomialmente redutível para D
Encontrar um algoritmo de tempo polinomial para um problema NP-completo significa que não há diferença qualitativa entre a complexidade de verificar uma solução proposta e encontrá-la em tempo polinomial