fundamentos de la computación tc4001cb.mty.itesm.mx/tc4001/tc4001-np-completos-agenda.pdf · en el...

Problemas NP-Completos TC4001 - p. 1/11

Fundamentos de la ComputaciónTC4001

Problemas NP-CompletosCentro de Manufactura / Centro de Sistema Inteligentes

ITESM

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 2/11

Introducción

■ Hasta ahora se han abordado problemas que ensu mayoría pueden resolverse en tiempopolinomial.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 2/11

Introducción

■ Hasta ahora se han abordado problemas que ensu mayoría pueden resolverse en tiempopolinomial.

■ Sin embargo, hay problemas, como el deencontrar en un grafo un ciclo de Hamilton, en elcual la única solución en apariencia esresolverlos en forma casi exhaustiva.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 2/11

Introducción

■ Hasta ahora se han abordado problemas que ensu mayoría pueden resolverse en tiempopolinomial.

■ Sin embargo, hay problemas, como el deencontrar en un grafo un ciclo de Hamilton, en elcual la única solución en apariencia esresolverlos en forma casi exhaustiva. En el casodel ciclo de Hamilton da una complejidadfactorial.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 2/11

Introducción

■ Hasta ahora se han abordado problemas que ensu mayoría pueden resolverse en tiempopolinomial.

■ Sin embargo, hay problemas, como el deencontrar en un grafo un ciclo de Hamilton, en elcual la única solución en apariencia esresolverlos en forma casi exhaustiva. En el casodel ciclo de Hamilton da una complejidadfactorial.

■ Lejos de intentar encontrar un algoritmopolinomial para el problema específico o para losproblemas que vengan, se ha optado por unapostura más radical:

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 2/11

Introducción

■ Hasta ahora se han abordado problemas que ensu mayoría pueden resolverse en tiempopolinomial.

■ Sin embargo, hay problemas, como el deencontrar en un grafo un ciclo de Hamilton, en elcual la única solución en apariencia esresolverlos en forma casi exhaustiva. En el casodel ciclo de Hamilton da una complejidadfactorial.

■ Lejos de intentar encontrar un algoritmopolinomial para el problema específico o para losproblemas que vengan, se ha optado por unapostura más radical: pensar en lo que se podráalguna vez llegar a hacer en lugar de lo queahora se puede hacer.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 3/11

Agenda Clase P

■ Definir el concepto de problema de decisión ycontrastarlo contra el problema de optimización(cuando hay lugar).

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 3/11

Agenda Clase P

■ Definir el concepto de problema de decisión ycontrastarlo contra el problema de optimización(cuando hay lugar). Mostrar algunos ejemplos:◆ Coloreo de Grafos◆ Calendarización de trabajos◆ Empacamiento◆ Subconjuntos◆ Satisfactibilidad◆ Agente viajero

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 3/11

Agenda Clase P

■ Definir el concepto de problema de decisión ycontrastarlo contra el problema de optimización(cuando hay lugar). Mostrar algunos ejemplos:◆ Coloreo de Grafos◆ Calendarización de trabajos◆ Empacamiento◆ Subconjuntos◆ Satisfactibilidad◆ Agente viajero

■ Definición de la clase P

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 4/11

Agenda Clase NP

■ Contrastrar entre resolver y verificar.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 4/11

Agenda Clase NP

■ Contrastrar entre resolver y verificar.■ Algoritmo no determinista.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 4/11

Agenda Clase NP

■ Contrastrar entre resolver y verificar.■ Algoritmo no determinista.■ Ejemplo

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 4/11

Agenda Clase NP

■ Contrastrar entre resolver y verificar.■ Algoritmo no determinista.■ Ejemplo■ Definición de la clase NP

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 4/11

Agenda Clase NP

■ Contrastrar entre resolver y verificar.■ Algoritmo no determinista.■ Ejemplo■ Definición de la clase NP■ P ⊆ NP

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 5/11

Agenda: Problemas NP-Completos

■ El concepto de reducción polinómica yreducibilidad

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 5/11

Agenda: Problemas NP-Completos

■ El concepto de reducción polinómica yreducibilidad

■ Definición de problema NP-Completo y deNP-Hard.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 5/11

Agenda: Problemas NP-Completos

■ El concepto de reducción polinómica yreducibilidad

■ Definición de problema NP-Completo y deNP-Hard.

■ Teorema de Cook: El problema de lasatisfactibilidad es NP-Completo

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 5/11

Agenda: Problemas NP-Completos

■ El concepto de reducción polinómica yreducibilidad

■ Definición de problema NP-Completo y deNP-Hard.

■ Teorema de Cook: El problema de lasatisfactibilidad es NP-Completo

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 5/11

Agenda: Problemas NP-Completos

■ El concepto de reducción polinómica yreducibilidad

■ Definición de problema NP-Completo y deNP-Hard.

■ Teorema de Cook: El problema de lasatisfactibilidad es NP-Completo

■ Lista de Karp

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 5/11

Agenda: Problemas NP-Completos

■ El concepto de reducción polinómica yreducibilidad

■ Definición de problema NP-Completo y deNP-Hard.

■ Teorema de Cook: El problema de lasatisfactibilidad es NP-Completo

■ Lista de Karp■ Teorema: Si un problema NP-Completo

cualquiera está en P, entonces P = NP .

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 5/11

Agenda: Problemas NP-Completos

■ El concepto de reducción polinómica yreducibilidad

■ Definición de problema NP-Completo y deNP-Hard.

■ Teorema de Cook: El problema de lasatisfactibilidad es NP-Completo

■ Lista de Karp■ Teorema: Si un problema NP-Completo

cualquiera está en P, entonces P = NP .■ Conjetura del millón de dolares: P = NP .

http://www.claymath.org/

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 6/11

Algoritmos de Aproximación

■ Enfoque: La solución exacta a un problema deoptimización es para fines prácticos inalcanzableen un tiempo razonable, pero una soluciónaproximada y rápida tiene sentido en elproblema y tiene un valor práctico.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 6/11

Algoritmos de Aproximación

■ Enfoque: La solución exacta a un problema deoptimización es para fines prácticos inalcanzableen un tiempo razonable, pero una soluciónaproximada y rápida tiene sentido en elproblema y tiene un valor práctico.

■ El concepto de Heurísticas de solución.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 6/11

Algoritmos de Aproximación

■ Enfoque: La solución exacta a un problema deoptimización es para fines prácticos inalcanzableen un tiempo razonable, pero una soluciónaproximada y rápida tiene sentido en elproblema y tiene un valor práctico.

■ El concepto de Heurísticas de solución.■ Heurísticas ejemplo para:

◆ TSP◆ Apareamiento mínimo

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 6/11

Algoritmos de Aproximación

■ Enfoque: La solución exacta a un problema deoptimización es para fines prácticos inalcanzableen un tiempo razonable, pero una soluciónaproximada y rápida tiene sentido en elproblema y tiene un valor práctico.

■ El concepto de Heurísticas de solución.■ Heurísticas ejemplo para:

◆ TSP◆ Apareamiento mínimo

■ Garantía de calidad de una heurística

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 7/11

Referencias Clásicas

■ La clase P fue introducida por Alan Cobham en:Cobham A: The intrinsic computationaldifficulty of functions. In Proceedings of theCongress for Logic, Methodology, and thePhilosophy of Science, pages 24-30.North-Holland. 1964.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 8/11

■ La clase P también fue independientementedefinida por Jack Edmonds que tambiénintrodujo la definición de NP y conjeturó queP 6= NP .

Edmonds, J: Paths, trees, and Flowers.Canadian Journal of Mathematics.17:449-467, 1965.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 9/11

El concepto de problema NP-Completo fue introducida por Step-hen Arthur Cook (Turing Award1982) dió la demostración de que elproblema de satisfactibilidad de ex-presiones 3-CNF era NP-Completo.

Cook, S: The complexity ofthe theorem proving procedu-res. Proceedings of the ThirdAnnual ACM Symposium onTheory of Computing. pages151-158. 1971.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 10/11

Richard Manning Karp (TuringAward 1985) introdujo una metodo-logía para reducción de problemasa otros y demostró una variedad deproblemas NP-Completos en:

Karp, R: Reducibility amongcombinatorial problems. Com-plexity of Computer Compu-tations, pages 85-103. Ple-num Press, 1972.

IntroduccionAgenda: Clase PAgenda: Clase NPAgenda:ProblemasNP-CompletosAgenda:Algoritmos deAproximacionReferencias

Problemas NP-Completos TC4001 - p. 11/11

Manindra Agrawal was born in May 1966,and since 2001 he has been a full professor atthe Indian Institute of Technology in Kanpur, In-dia. For some years he has been interested infinding a polynomial time algorithm to test whet-her a given number is prime. Although randomalgorithms can solve this problem with high cer-tainty in polynomial time, it remained a long-standing challenge to find a method that worksin every case.

To the great surprise of the experts, Agrawal

solved this problem in August 2002, working to-

gether with two undergraduate students: Neeraj

Kayal and Nitin Saxena. Their proof establishes

the correctness of a conjecture made in 1999

by Agrawal and Biswas.