Calculabilité et complexité Cours no4

Calculabilite´ et complexite´oCours n 4Nicolas (Miki) Hermann´LIX, Ecole Polytechniquehermann@lix.polytechnique.fr´ ´Miki Hermann Calculabilite et complexite (4)Reductions´Les classes P, NP, PSPACE, EXP, ... contiennent une infinite´ delangages.Question : Comment classifier des langages dans une classe?Reponse´ : Par leur difficulte´ de solution.Question : Comment dire que le langage/probleme` B est au moinsaussi difficile que le langage/probleme` A?´Reponse´ : Par le concept de reduction.´ ´Miki Hermann Calculabilite et complexite (4)´ ´Definition de la reduction de Karp (many one)`Soit A et B deux langages/problemes A est polynomialement∗ ∗´ `(logarithmiquement) reductible a B s’il existe une fonction R: Σ → Σ´calculable par une machine de Turing deterministe en tempspolynomial (en espace logn), telle que pour chaque mot x la conditionsuivante est satisfaite :x∈ A si et seulement si R(x)∈ BR s’appelle une reduction´ polynomiale (logarithmique) de A a` BReductions´A se reduit´ a` B s’il existe une transformation R, telle que pour chaqueentree´ x∈ A elle calcule l’entree´ equiv´ alente R(x)∈ B.La transformation R ne peut pas etreˆ trop couteuseˆ !´ ´Miki Hermann Calculabilite et complexite (4)Reductions´A se reduit´ a` B s’il existe une transformation R, telle que pour chaqueentree´ x∈ A elle calcule l’entree´ equiv´ alente R(x)∈ B.La transformation R ne peut pas etreˆ trop couteuseˆ !´ ´Definition de la reduction de Karp (many one)`Soit A et B ...