D´emonstration que le probl`eme HAMD est NP-complet Alexandre Blondin Mass´e D´ epartement d’informatique Universit´ e du Qu´ ebec ` a Montr´ eal 23 octobre 2014 Cours INF7440 D´epartement d’informatique A. Blondin Mass´ e (UQAM) 23 octobre 2014 1 / 4 HAMD est NP-complet Th´eor`eme Le probl`eme HAMD est NP-complet. I Il est facile de voir que HAMD est de classe NP; A. Blondin Mass´ e (UQAM) 23 octobre 2014 2 / 4 HAMD est NP-complet Th´eor`eme Le probl`eme HAMD est NP-complet. I Il est facile de voir que HAMD est de classe NP; I La r´ eduction est par contre plus complexe. A. Blondin Mass´ e (UQAM) 23 octobre 2014 2 / 4 HAMD est NP-complet Th´eor`eme Le probl`eme HAMD est NP-complet. I Il est facile de voir que HAMD est de classe NP; I La r´ eduction est par contre plus complexe. I En g´en´eral, on montre que k-VCD HAMD A. Blondin Mass´ e (UQAM) 23 octobre 2014 2 / 4 R´eduction A. Blondin Mass´ e (UQAM) w x z y 23 octobre 2014 3 / 4 R´eduction Ww,z A. Blondin Mass´ e (UQAM) Ww,y w x z y Ww,x 23 octobre 2014 Wx,y 3 / 4 R´eduction Ww,z A. Blondin Mass´ e (UQAM) Ww,y w x z y Ww,x 23 octobre 2014 Wx,y 3 / 4 R´eduction Ww,z Ww,y w x z y Ww,x s1 A. Blondin Mass´ e (UQAM) Wx,y s2 23 octobre 2014 3 / 4 R´eduction Ww,z Ww,y w x z y Ww,x s1 A. Blondin Mass´ e (UQAM) Wx,y s2 23 octobre 2014 3 / 4 R´eduction Ww,z Ww,y w x z y Ww,x s1 A. Blondin Mass´ e (UQAM) Wx,y s2 23 octobre 2014 3 / 4 R´eduction Ww,z Ww,y w x z y Ww,x s1 A. Blondin Mass´ e (UQAM) Wx,y s2 23 octobre 2014 3 / 4 R´eduction Ww,z Ww,y w x z y Ww,x s1 A. Blondin Mass´ e (UQAM) Wx,y s2 23 octobre 2014 3 / 4 R´eduction Ww,z Ww,y w x z y Ww,x s1 A. Blondin Mass´ e (UQAM) Wx,y s2 23 octobre 2014 3 / 4 R´eduction Ww,z Ww,y w x z y Ww,x s1 A. Blondin Mass´ e (UQAM) Wx,y s2 23 octobre 2014 3 / 4 R´eduction Ww,z Ww,y w x z y Ww,x s1 A. Blondin Mass´ e (UQAM) Wx,y s2 23 octobre 2014 3 / 4 R´eduction Ww,z Ww,y w x z y Ww,x s1 A. Blondin Mass´ e (UQAM) Wx,y s2 23 octobre 2014 3 / 4 R´eduction Ww,z Ww,y w x z y Ww,x s1 A. Blondin Mass´ e (UQAM) Wx,y s2 23 octobre 2014 3 / 4 R´eduction Ww,z Ww,y w x z y Ww,x s1 A. Blondin Mass´ e (UQAM) Wx,y s2 23 octobre 2014 3 / 4 R´eduction (suite) I On sait d´ej`a que HAMD est de classe NP; A. Blondin Mass´ e (UQAM) 23 octobre 2014 4 / 4 R´eduction (suite) I On sait d´ej`a que HAMD est de classe NP; I On constate que la transformation est polynomiale; A. Blondin Mass´ e (UQAM) 23 octobre 2014 4 / 4 R´eduction (suite) I On sait d´ej`a que HAMD est de classe NP; I On constate que la transformation est polynomiale; I Pour chaque couverture des arˆ etes, on peut construire un cycle hamiltonien; A. Blondin Mass´ e (UQAM) 23 octobre 2014 4 / 4 R´eduction (suite) I On sait d´ej`a que HAMD est de classe NP; I On constate que la transformation est polynomiale; I Pour chaque couverture des arˆ etes, on peut construire un cycle hamiltonien; I ` chaque cycle hamiltonien, on peut lui associer une A couverture des arˆ etes par les sommets. A. Blondin Mass´ e (UQAM) 23 octobre 2014 4 / 4
© Copyright 2024 ExpyDoc