Calculabilité et complexité Cours no4

De
Publié par

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 ...
Publié le : samedi 24 septembre 2011
Lecture(s) : 15
Nombre de pages : 60
Voir plus Voir moins
Calculabilit´eetcomplexite´ Cours no4
Nicolas (Miki) Hermann
´ LIX, Ecole Polytechnique
hermann@lix.polytechnique.fr
iMikHeramnnaCcllubaliti´eteocpmelixt´e(4)
Les classesP,NP,PSPACE,EXP une infinit ´e . . contiennent, . de langages.
Question : ?Comment classifier des langages dans une classe Re´ ponse : solution. dePar leur difficulte´ Question :Comment dire que le langage/proble` meBest au moins aussi difficile que le langage/proble` meA? R´eponse:Par le concept dere´ duction.
R´ucedsitnoanrmHekiMi(4)it´eplextcom´teeibilucalCnla
ionpducter´eleungoraell(moailonyBM`aeA)dueiqhmitluclaCnnamreHikionsuivanaconditisiafti:eetsesttaleeuntmeAsxtsieasRlepp(RisB)xbalitie´teocpmelxit´e(4)
Aude´a`tiersBs’il existe unetransformationR, telle que pour chaque entreexAeelullccaleeluqvilanetn´reee´teR(x)B. ´ La transformationRentuepoptrˆucosˆpareete!uste
´eRctdunsioBtedtieAgngaxual(manKarpe)Soy-onde´raledednoitcuD´ontinietnr)e´udtcbiela`(logarithmiquemeloptmonyelaitnem/pesblrome`eessAd´etringdeTuhinemecaranulbpeucalalcΣΣR:ontincofenuetsixelisBquemotxlepourchat,leeluqcalego)n(ealspnelypominotneespmeimretsin
Re´ductions Aauite`dr´seBs’il existe unetransformationR, telle que pour chaque entre´ exAetnelaviuqe´e´etrenllecualecellR(x)B. La transformationR teuse !ne peut pas etre trop couˆ ˆ D ´ finition de la re´ duction de Karp (many-one) e SoitAetB mesdeux langages/proble`Aestpolynomialement (logarithmiquemente`at)irb´leducBs’il existe une fonctionR: ΣΣe calculable par une machine de Turing d ´ terministe entemps polynomial(enespacelogn), telle que pour chaque motxla condition suivante est satisfaite : xAsi et seulement siR(x)B Rs’appelle uner´eductionpolynomiale (logarithmique) deA`aB Miki Hermann Calculabilite´ et complexite´ (4)
eledreapL´eidR0(CxA(y)BR0By(R)xxAvu:er´uxnaiontteatreiaftuaflIC))x(RsnRdu´eioctucedontiogslitarqimh.seuikiMmreHannCalculabilit´eectmolpxetie´4(
Les re´ ductions se composent.
Th´eoreme ` SiRal´retsontiuceddeAa`BetR0la re´ de ductionB`aC, alors la compositionRR0 duction deest une re´Aa`C.
)
Lesr´eductionssecomposent.
Th ´ ` me eore SiR de ductionest la re´Aa`BetR0alondeuctir´edB`aC, alors la compositionRR0 de ductionest une re´A`aC.
)(4´eitexplomctee´tilibaluclaannCHermMiki
Ilfautfaireattentionauxr´eductionslogarithmiques.
L’ide´ e de la preuve :
xAR(x)B yBR0(y)C xAR0(R(x))C
tcoisnRe´ud
e´telitilubaaCclmanniHerMik
Conventio´duct=r´etioneducaimoelpnoinylo n :r Notation :ABouABsiAiu`taes´rdeB. Vous pouvez aussi voir ApmBouApmBulisgarpminaqtexndu´eioctditerunmany-one polynomiale.
4)e(t´xilempconostiucedR´
mpl´Coeetud4()
On peut prendre pourCles classesNP,PSPACE,EXP aussi, . et . .P sionutiliselesr´eductionslogarithmiques.
SoitCme`e/pgeblro´eitexplgaanel.LalcenumocedessAest dit C-difficile mesi pour chaque langage/proble`B∈ C,B`saitdu´eerA. Si le langage/proble` meAestC-difficile etA∈ C, on dit queAest C-complet. Probl`emesC `a re´ mes les plus difficiles soudre-complets = les proble` dans la classeC
lpxetie´t´eetcomculabililaCnnamreHikiM
edR´taellspsosleae,C=CCtssr0Mn.o0cCtilHoiskemsapearrCra´nenduulcltcincoreesxAdtesceiCyttcs-emPo.lepleptoariontsiisqiuSeiCo0n-sccolmeitnodecuratilsgoues.hmiqve:EPreutsiael´cbsaelLi.pNm,eLl,tPesoecsel(o4t)cxointL´sr´ars
est ductionsclose par re´siABetB∈ C
p
Une classeC A∈ C.
s
implique
esontclos,EXP,...udtcoisnseaprre´scLesslasipoontiSP,PECAPPNseNoc,Porsontiuc
asseesclC0sosCetposorPSnlitioilaroCsC=ocpmel,tsiqueC0-mpletaintseAoc-Coitctesnrrpadu´eclntesos
Preuve : Exercice de style.
Proposition Les classesNP,coNP,PSPACE,EXP sont closes par re´ ductions., . . . Les classesP,L,NLsont closes par reductions logarithmiques. ´
Une classeCest ductionsclose par re´siABetB∈ Cimplique A∈ C.
(4)it´eplexmoctee´tilibalucalnCanrmHekiMi0.Rsne´udtcoi
tyleedes.ueevrPcrciE:exreHikiM´t(eelixocpme´teilitulabCalcmann
Proposition Si les classesCetC0onslotcspsera´rdecuitnoestAestC-complet 0 ainsi queC0-complet, alorsC=C.
4)
Une classeCest ductionsclose par re´siABetB∈ Cimplique A∈ C.
Proposition Les classesNP,coNP,PSPACE,EXP,.soseaprr..ostnlc.nsdu´eioct Les classesP,L,NL ductions logarithmiques.sont closes par re´
´Rcudenoits
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.