Calculabilité et complexité Cours no5

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 ) ...