Bonjour, je viens poster sur ce forum car je ne comprends pas comment faire certaines démonstration de mon cours.
Voilà ce que je dois chercher à faire pour mon cours :
(1) Donnez un exemple de réduction d’un problème décidable (codé par un langage récursif) vers un problème indécidable (codé par un langage non récursif).
(2) Soit L un langage, et soit L5 l’ensemble des mots de L dont la longueur est supérieure ou égale à 5 :
L5 = { w dans L , |w| >= 5 } .
(a) Montrez que si L est P, alors L5 est P.
(b) Montrez que si L est NP, alors L5 est NP.
© Supposons qu’on connaisse un mot w appartenant à L5. Montrez que si L est NP-complet, alors L5 est NP-complet.
Merci d’avance pour vos explications !
-----