np-complexo

Projeto e
Análise de Algoritmos
Problemas N P-Completo e
Algoritmos Aproximados
Antonio Alfredo Ferreira Loureiro [e-mail] http://www.dcc.ufmg.br/~loureiro

UFMG/ICEx/DCC

PAA

·

Problemas NP-Completo e Algoritmos Aproximados

1

Introdução
• Problemas intratáveis ou difíceis são comuns na natureza e nas áreas do conhecimento. • Problemas “fáceis”: resolvidos por algoritmos polinomiais.
• Problemas “difíceis”: no momento, conhecemos apenas algoritmos exponenciais para resolvê-los.
• A complexidade de tempo da maioria dos problemas é polinomial ou exponencial.

UFMG/ICEx/DCC

PAA

·

Problemas NP-Completo e Algoritmos Aproximados

2

Introdução
• Polinomial: função de complexidade é O(p(n)), onde p(n) é um polinômio. – Por exemplo, pesquisa binária (O(log n)), pesquisa seqüencial (O(n)), ordenação por inserção (O(n2)), e multiplicação de matrizes (O(n3)).
• Exponencial: função de complexidade é O(cn), c > 1.
– Por exemplo, problema do caixeiro viajante (PCV) (O(n!)).
– Mesmo problemas de tamanho pequeno a moderado não podem ser resolvidos por algoritmos não-polinomiais.

UFMG/ICEx/DCC

PAA

·

Problemas NP-Completo e Algoritmos Aproximados

3

Problemas N P-Completo
• A teoria de complexidade a ser apresentada não mostra como obter algoritmos polinomiais para problemas que demandam algoritmos exponenciais, nem afirma que não existem.
• É possível mostrar que os problemas para os quais não há algoritmo polinomial conhecido são computacionalmente relacionados.
• Formam a classe conhecida como N P.
• Propriedade: um problema da classe N P poderá ser resolvido em tempo polinomial se e somente se todos os outros problemas em N P também puderem.
• Este fato é um indício forte de que dificilmente alguém será capaz de encontrar um algoritmo eficiente para um problema da classe N P.

UFMG/ICEx/DCC

PAA

·

Problemas NP-Completo e Algoritmos Aproximados

4

Classe N P: Problemas “Sim/Não”
•