Machine de Turing et problèmes NP Complets

Bonjour à tous et à toutes !

Voilà j'ai un exercice à faire concernant la Machine de Turing et les problèmes NP.

J'ai quelques idées de réponses mais j'aimerais que vous m'aiguillez .

Machine de Turing :

1) On utilise la machine de Turing unaire ( l'alphabet est limité au bâton). Montrez que la fonction f : IN --> IN définie par f(n) = 2n est Turing calculable.

Alors pour celle - là je pense qu'il faille créer la liste d'instructions nécessaire et dire que par conséquent il existe un nombre (nombre de Godel) indexant cette liste d'instruction.

2) Même question avec l'alphabet binaire E = {0,1}

Alors là ... Je sais que l'alphabet n'importe peux. Faut - il dire qu'il existe une bijection entre ces deux alphabets ? Faut - il en faire la preuve ?

3) Calculez les fonctions de complexité dans les deux cas.

La complexité revient - elle à compter le nombre d'instruction pour f(n) = 2n en fonction de l'alphabet ? (qui doit contenir moins d'instruction, j'imagine , pour la seconde )


Problèmes NP.

1) Montrez que
Problème du cycle Hamiltonien
Problème du voyageur de commerce
sont deux problèmes de la classe NP

-> u___u comment démontrer ça ?
Solutions infinies non dénombrable ?


2) Montrez que le problème du cycle hamiltonien est un cas particulier du problème
du voyageur de commerce.

Bas le voyageur du commerce à la contrainte supplémentaire de trouver le cout minimum.
M'enfin bon je pense pas que ce soit une réponse valable.

3) Décrivez comment une machine de Turing pourrait transformer l'encodage d'une instance CH en encodage d'une instance VC ? Quelle en serait la complexité ?

-> Pas d'idée

4) Déduisez que si VC € P alors CH € P

-> Pas d'idée non plus


Je vous remercie encore d'y avoir passé du temps