Problème de complexité

Problème résolu!

Qu’est-ce que tu as essayé, et où est-ce que tu bloques ?

Pour la question 2.a, j’aurais dit que la comparaison d’une longueur de mot reste polynomiale mais je ne sais pas du tout quoi faire pour la 2.b et 2.c

Je pense que l’esprit de ces questions est d’essayer de suivre précisément les définitions que tu as dû voir dans ton cours. Une première piste pourrait être d’essayer d’écrire un peu plus précisément l’idée que tu as pour la question 2.a, afin de voir pourquoi ça démontre bien ce que tu veux démontrer. Je pense qu’une fois la question 2.a. plus précisément rédigée, et en regardant dans ton cours la définition de la classe NP tu devrais voir une similitude entre la question 2.a et la 2.b qui te donnera peut-être la bonne idée pour la suite.

Bonjour, j’ai effectivement réussi à faire la 2.a et 2.b en faisant une réduction de L5 sur L, cependant je ne vois pas l’importance de l’hypothèse 'Supposons qu’on connaisse un mot w appartenant à L5. Montrez que si L est NP-complet, alors L5 est NP-complet.’, pour la 2.c l’idée est de faire une réduction de L sur L5 mais quelle est la nécessité de cette hypothèse ?

Pour la question 1, ma réponse précédente est-elle correcte ou érronée?

Merci de vos réponses.

Je vois, vous m’avez effectivement bien aidé !

Merci, problème résolu.

C’est tout pile la réduction que l’on pouvait attendre oui !

Bien vu, effectivement ça vaut le coup de détailler un peu plus pourquoi les points en gras ne posent pas de problème. Dans ce que j’ai décrit plus haut sur la réduction, j’avais omis de préciser que le calcul de $f(w)$ doit se faire en temps polynomial (toujours en la taille de $w$). Il reste donc à justifier que l’on peut vérifier si un mot de longueur strictement inférieure à $5$ appartient à $L$ en temps polynomial (en sa longueur). Je te laisse réfléchir à cette question…

Pour le reste je pense que tu as lancé toutes les bonnes idées, ne restera qu’à bien rédiger tout ça !

C’est un peu dommage d’avoir supprimé la question et tes réponses intermédiaires… mais bon, ravi que ça ait pu aider au moins une personne.

Voici l’énoncé complet, peut-être cela servira t’il aux autres étudiants en quête d’aide.

Calculabilité Complexité

Devoir à rendre par e-mail au plus tard le 22/05/2020 à 20h00 (1) On sait que lorsqu’on a une réduction d’un premier langage L1 vers un deuxième langage L2, si L2 est récursif (décidable), alors L1 le sera aussi. A-t-on l’implication réciproque ? Si L1 est récursif (décidable), alors L2 doit-il aussi l’être ? Si vous pensez que c’est vrai, expliquez pourquoi. Si vous pensez que c’est faux, 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.