Très bref corrigé du CC no. 2 de novembre 2011.

Q1: J'écris ici > et _ pour les symboles "début de bande" et
"blanc". On définit les nouveaux symboles < et # qui servent de
substituts à > et _.

On va d'abord de façon non déterministe se placer à l'intérieur du mot
w et insérer les nouveaux symboles < et #. On a donc sur la bande
>_u<#v avec uv=w. On procède alors comme dans l'exercice fait en début
de TD:
(a) On se place en # et on fait tourner sur le mot v la MTND qui
    décide L2, avec les modifications suivantes:
      + dans les transitions (p,a,q,b) de cette MTND, on remplace > et
      _ par < et # respectivement;
      + on introduit une transition supplémentaire: chaque fois qu'on
        lit un _ sur la bande, on le remplace par # sans changer
        d'état.
(b) Si le résultat est n, on termine sur "non"; si c'est y, on passe à
    la suite.
(c) On efface < et tout ce qu'il y a à droite, jusqu'à ce qu'on arrive
    sur un _, on revient alors en début de bande sur le _ après >, et
    on fait tourner la MTND qui décide L1.
(d) Si le résultat est n, on termine sur "non"; si c'est y, on termine
    sur "oui".

La complexité est NP, pour les mêmes raisons que dans l'exercice de
TD. On obtient bien un "oui" si pour un certain choix de transitions
la 2e machine dit oui sur v et la 1e dit oui sur u, donc si u est dans
L1 et v dans L2, et effectivement w est dans L1L2 si pour un certain
choix de décomposition w = uv on a u dans L1 et v dans L2.

Q2. (i) Soit X un problème NP-complet. Si L est EXP, alors comme le
problème NP-complet X est "au moins aussi difficile" que le problème
NP L, X est au moins EXP. Une autre façon de la voir, est que L se
réduit polynomialement sur X, donc si X avait une complexité plus
petite que EXP, cette réduction permettrait de décider L en un temps
moindre que EXP. Mais on a vu que NP est inclus dans EXP: tout
problème NP peut être résolu en temps EXP sur une MT déterministe,
donc la complexité de X n'est pas plus grande que EXP; étant au moins
aussi grande que EXP, elle est ainsi EXP.

(ii) NP contient P, donc les problèmes P font partie de NP, leur
complexité n'est pas affectée par celle de L.

Q3. (i) En prenant la MTND polynomialement bornée qui décide le
complément de L, et en intervertissant "y" et "n", on obtient une MTND
polynomialement bornée telle que pour un mot w:
- si w est dans L, tout choix de transitions amènera à "y";
- si w n'est pas dans L, il y a un choix de transitions amenant à "n".

(ii) Supposons P=NP, on aurait alors co-NP=co-P (co-P: classe des
langages complémentaires des langages P). Mais on a vu que P=co-P (si
dans la MT polynomialement bornée qui décide un langage, on
intervertit "y" et "n", alors elle décide le complément et reste
polynomialement bornée). On a alors co-NP=co-P=P=NP, ce qui contredit
l'hypothèse co-NP=/=NP, donc la supposition de départ est fausse, et
P=/=NP.

Q4. L'exécution de la MT M sur le langage w est simulée par la MT
universelle U à 3 bandes, où la 1e bande contient le codage du contenu
de la bande de M (avec position du curseur), la 2e le codage de la
liste des transitions de M, et la 3e le codage de l'état courant de
M. On modifie cette exécution pour que la 3e bande contienne la suite
des états visités (séparés par des blancs). Donc chaque fois qu'on
change d'état, au lieu de l'effacer sur la 3e bande, on le laisse et
on écrit le nouvel état à droite. Appelons U' cette MT universelle
modifiée.

Pour que M passe par tous ses états, il faut qu'elle passe par l'état
final, donc qu'elle s'arrête. Donc si la simulation de l'exécution de
M sur w s'arrête, on ajoute dans U' un étape supplémentaire: vérifier
que chaque état apparaissant dans la liste de transitions sur la 2e
bande apparaît bien sur la 3e bande. Si un état n'apparaît pas, on
arrête la vérification et on se met sur un état bouclant. Si à la fin
de la 2e bande, on a vérifié que tous les états se retrouvent sur la
3e, on s'arrête alors sur un "oui".

On a bien 3 cas:
- M ne s'arrête pas sur w: U' ne s'arrête pas.
- M s'arrête sur w mais ne passe pas par un certain état: U' est
  envoyée sur un état bouclant.
- M s'arrête sur w en étant passé par tous les états: U' s'arrête sur
  "oui".