Je vais me permettre de pousser une petite gueulante car la « vraie » définition
de NP-complet n'est pas celle là (cf le lien wikipedia).
Tout d'abord, il y a les machines de Turing déterministes.
---
On a
- un ruban sur laquelle il y a des caractères écrits (alphabet fini),
- une tête de lecture à un endroit précis;
- un automate fini.
L'automate lit le caractère sous la tête de lecture et en fonction du résultat
et de son état initial, il écrit quelque chose et se déplace à droite ou à gauche.
La machine peut aussi s'arêter.
Certaines machine permettent de répondre à des questions. On écrit sur le
ruban la question et à la fin, la machine s'arête en écrivant oui ou non.
---
Il y a aussi les machines non déterministes.
---
À chaque la machine peut « se délocaliser » -- ce terme est de moi.
C'est à dire qu'au lieu de passer dans l'état 18, d'écrire un r et d'aller à gauche,
elle effectue plusieurs transition en même temps: elle est aussi passée dans
l'état 34, a écrit un z et à déplacé la tête de lecture à droite.
À l'étape d'après, toutes les « machines délocalisées » effectuent simultanément
leur transition.
Une telle machine répond oui si *une* des machines délocalisées répond oui
et elle répond non si *toutes* les machines délocalisées répondent non.
Ça, si c'est pas du massivement parallèle mon gars!
---
Comme le temps nous intéresse, on définit des classes de complexité.
La classe P est l'ensemble des problèmes tels qu'il existe une machine
déterministe qui répond en temps polynomial.
La classe NP est l'ensemble des problèmes tels qu'il existe une machine
non-déterministe qui répond en temps polynomial.
Le problème, c'est que manipuler une machine non déterministe, c'est un brin
chiant. Heureusement, il un théorème qui dit qu'un problème est NP s'il existe
une machine déterministe avec oracle polynomial qui vérifie la solution en temps
polynomial. En gros, on donne la solution à la machine et elle vérifie que c'est
bien une solution.
Les gens ont tendance à préférer cette seconde version mais elle n'est pas
toujours adaptée comme pour le voyageur de commerce. Si la question
est:« l'optimal est-il de longueur inférieur à k », il est très facile de faire une
machine non déterministe. À chaque étape, elle prend tous les chemins
possibles simultanément. Si une des machines trouve un chemin mieux que k,
elle dit oui et si son chemin est plus grand que k, elle dit non.
Un exemple de problème qui se traite vraiment bien avec la seconde méthode,
c'est le problème SAT (http://fr.wikipedia.org/wiki/Probl%C3%A8me_SAT(...)).
Si une formule SAT est satisfiable, il existe une assignation des variables qui
la rend vraie. Si on se donne cette assignation, il est alors trivial de vérifier que
la formule est effectivement satisfiable.
[^] # Re: Algorithme génétique ?
Posté par fmaz fmaz . En réponse à la dépêche Améliorer les performances du noyau avec un algorithme génétique. Évalué à 7.
de NP-complet n'est pas celle là (cf le lien wikipedia).
Tout d'abord, il y a les machines de Turing déterministes.
---
On a
- un ruban sur laquelle il y a des caractères écrits (alphabet fini),
- une tête de lecture à un endroit précis;
- un automate fini.
L'automate lit le caractère sous la tête de lecture et en fonction du résultat
et de son état initial, il écrit quelque chose et se déplace à droite ou à gauche.
La machine peut aussi s'arêter.
Certaines machine permettent de répondre à des questions. On écrit sur le
ruban la question et à la fin, la machine s'arête en écrivant oui ou non.
---
Il y a aussi les machines non déterministes.
---
À chaque la machine peut « se délocaliser » -- ce terme est de moi.
C'est à dire qu'au lieu de passer dans l'état 18, d'écrire un r et d'aller à gauche,
elle effectue plusieurs transition en même temps: elle est aussi passée dans
l'état 34, a écrit un z et à déplacé la tête de lecture à droite.
À l'étape d'après, toutes les « machines délocalisées » effectuent simultanément
leur transition.
Une telle machine répond oui si *une* des machines délocalisées répond oui
et elle répond non si *toutes* les machines délocalisées répondent non.
Ça, si c'est pas du massivement parallèle mon gars!
---
Comme le temps nous intéresse, on définit des classes de complexité.
La classe P est l'ensemble des problèmes tels qu'il existe une machine
déterministe qui répond en temps polynomial.
La classe NP est l'ensemble des problèmes tels qu'il existe une machine
non-déterministe qui répond en temps polynomial.
Le problème, c'est que manipuler une machine non déterministe, c'est un brin
chiant. Heureusement, il un théorème qui dit qu'un problème est NP s'il existe
une machine déterministe avec oracle polynomial qui vérifie la solution en temps
polynomial. En gros, on donne la solution à la machine et elle vérifie que c'est
bien une solution.
Les gens ont tendance à préférer cette seconde version mais elle n'est pas
toujours adaptée comme pour le voyageur de commerce. Si la question
est:« l'optimal est-il de longueur inférieur à k », il est très facile de faire une
machine non déterministe. À chaque étape, elle prend tous les chemins
possibles simultanément. Si une des machines trouve un chemin mieux que k,
elle dit oui et si son chemin est plus grand que k, elle dit non.
Un exemple de problème qui se traite vraiment bien avec la seconde méthode,
c'est le problème SAT (http://fr.wikipedia.org/wiki/Probl%C3%A8me_SAT(...)).
Si une formule SAT est satisfiable, il existe une assignation des variables qui
la rend vraie. Si on se donne cette assignation, il est alors trivial de vérifier que
la formule est effectivement satisfiable.
wala wala wala
Frédéric