Calculabilite´ et complexite´oCours n 5Nicolas (Miki) Hermann´LIX, Ecole Polytechniquehermann@lix.polytechnique.fr´ ´Miki Hermann Calculabilite et complexite (5)Theor´ eme`3DM estNP complet.Indication pour la preuve :3DM∈NP : choix et test.Borne infer´ ieure : reduction´ a` partir de 3SAT.CouplageCouplage tripartiProbleme:` 3 DIMENSIONAL MATCHING (3DM)Entree:´ Trois ensemblesB (garc¸ons),G (filles) etH (maisons), avec|B|=|G|=|H|=n, et une relationT ⊆B×G×H.Question: Existe t il un ensemble S⊆T den triples disjoints?´ ´Miki Hermann Calculabilite et complexite (5)Indication pour la preuve :3DM∈NP : choix et test.Borne infer´ ieure : reduction´ a` partir de 3SAT.CouplageCouplage tripartiProbleme:` 3 DIMENSIONAL MATCHING (3DM)Entree:´ Trois ensemblesB (garc¸ons),G (filles) etH (maisons), avec|B|=|G|=|H|=n, et une relationT ⊆B×G×H.Question: Existe t il un ensemble S⊆T den triples disjoints?Theor´ eme`3DM estNP complet.´ ´Miki Hermann Calculabilite et complexite (5)CouplageCouplage tripartiProbleme:` 3 DIMENSIONAL MATCHING (3DM)Entree:´ Trois ensemblesB (garc¸ons),G (filles) etH (maisons), avec|B|=|G|=|H|=n, et une relationT ⊆B×G×H.Question: Existe t il un ensemble S⊆T den triples disjoints?Theor´ eme`3DM estNP complet.Indication pour la preuve :3DM∈NP : choix et test.Borne infer´ ieure : reduction´ a` partir de 3SAT.´ ´Miki Hermann Calculabilite et complexite (5)Theor´ eme`2.5PERFECT MATCHING est dansP pour un algorithme en tempsO(n ) ...
Proble` me: )3 (3 Entre´e:Trois ensemblesBno¸c,)sar(gG(filles) etH(maisons), avec |B|=|G|=|H|=n, et une relationT⊆B×G×H. Question:Existe-t-il un ensembleS⊆Tden ?triples disjoints
Probl`eme: )3 (3 Entre´e:Trois ensemblesB(garc¸ ons),G(filles) etH(maisons), avec |B|=|G|=|H|=n, et une relationT⊆B×G×H. Question:Existe-t-il un ensembleS⊆Tden ?triples disjoints
Indication pour la preuve : 3DM∈NP: choix et test. Borne infe´ rieure : re´ ductio ` artir de 3 . n a p
Th ´ ` eoreme 3DMestNP-complet.
´e(5exitompl
P bl ` : )3 (3 ro eme Entre´e:Trois ensemblesB)¸,onrscga(G(filles) etH(maisons), avec |B|=|G|=|H|=n, et une relationT⊆B×G×H. Question:Existe-t-il un ensembleS⊆Tdentriples disjoints ?
Probl`eme: Entr´ee:Deux ensemblesB(garc¸ ons) etG(filles), avec|B|=|G|=n, et une relationT⊆B×G. Question:Existe-t-il un ensembleS⊆Tden ?couples disjoints
The´ore`me PERFECT MATCHINGest dansPpour un algorithme en tempsO(n2.5).
Proble` me: Entr´ee:Deux ensemblesBno¸cte)srag(G(filles), avec|B|=|G|=n, et une relationT⊆B×G. Question:Existe-t-il un ensembleS⊆Tdencouples disjoints ?