La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin