Resumo sobre problemas P e NP PDF

Preview

Summary

Resumo sobre problemas P e NP...

Description

Os materiais (Slide e vídeo aula) discorreram sobre otimização, problemas de decisão e classes P e NP onde pode ser observado que: O problema de otimização é um problema em que em que cada solução possível tem um valor associado e desejamos encontrar a melhor solução com relação a esse valor. Todo problema para o qual existe um algoritmo polinomial é dito ser tratável, ao contrário intratável Problemas de decisão são problemas em que a resposta é simplesmente SIM ou NÃO Ex: O grafo X é um grafo euleriano? É possível formar um problema de otimização como um problema de decisão impondo que um limite sobre o valor a ser otimizado. A teoria da complexidade não se aplica diretamente a problemas de otimização, mas sim a problemas de decisão. A classe P é formada por problemas de decisões tratáveis, isto é, que podem ser resolvidos por um algoritmo polinomial. EX: o problema do grafo Euleriano pertence a classe P (pode ser resolvido usando um algoritmo polinomial) A classe NP é formada por problemas de decisão que possuem um verificador polinomial para a resposta sim. NP denota o conjunto de linguagens que podem ser aceitas em tempo polinomial por uma máquina de Turing não determinística. NP não significa não polinomial, significa tempo polinomial não determinístico. Um problema de decisão está em NP se existe um algoritmo A tal que: - Para qualquer instância X do problema com resposta sim, existe um certificado Y, tal que A(X,Y) devolve sim. - A consome tempo polinomial em |X| P = NP? Até o momento ainda não foi demonstrado Mas a maioria dos pesquisadores acreditam que P não é igual a NP Dado dois problemas A e B, uma redução de A para B é um algoritmo polinomial que resolve A utilizando B. Um problema de decisão é NP-Completo se:

O problema do 3-SAT é NP-completo primeiramente foi demonstrado que ele é NP e depois fazer a redução de SAT para 3-SAT Um problema NP-completo é um problema para o qual é improvável que exista um algoritmo eficiente. Deve-se buscar então heurística ou aproximações para resolvê-los....