Au passage, tu n'as pas expliqué le point sur lequelle j'ai fait une boulette : la completude ;-) (le reste etant bon et etant en gros ce que tu dis, en moins expliqué, en tout cas)
Ensuite, L'explication pas les machines de turing est une explication, et pas forcément l'unique solution pour expliquer le probleme.
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.
Un problème NP est un probleme "Non-déterministe Polynomial", c'est a dire qu'il existe une machine de turing non déterministe qui résoud le problème (d'apres ta propre définition). Or, une "machine de turing non déterministe" est équivalent à "une machine déterministe polynomial avec oracle" et pas "une machine déterministe avec oracle polynomial" (c'est la machine déterministe qui est polynomial, pas l'oracle). Je pense que c'est ce que tu voulais dire mais que tu t'es mal exprimé.
Pour finir, il existe en théorie des machines de turing non déterministe. Elles sont basé sur "l'ordinateur à ADN", c'est a dire qu'on modelise le probleme sous forme ADN, on met tout dans une grosse bassine et on recupere le résultat (en temps polynomial). Le problème, c'est que si c'est en temps polynomial, ca semble etre en espace exponentiel, ce qui arrange pas vraiment le probleme (et gerer des tonnes d'ADN, c'est pas vraiment réaliste...).
[^] # Re: Algorithme génétique ?
Posté par TeXitoi (site web personnel) . En réponse à la dépêche Améliorer les performances du noyau avec un algorithme génétique. Évalué à 2.
Au passage, tu n'as pas expliqué le point sur lequelle j'ai fait une boulette : la completude ;-) (le reste etant bon et etant en gros ce que tu dis, en moins expliqué, en tout cas)
Ensuite, L'explication pas les machines de turing est une explication, et pas forcément l'unique solution pour expliquer le probleme.
Un problème NP est un probleme "Non-déterministe Polynomial", c'est a dire qu'il existe une machine de turing non déterministe qui résoud le problème (d'apres ta propre définition). Or, une "machine de turing non déterministe" est équivalent à "une machine déterministe polynomial avec oracle" et pas "une machine déterministe avec oracle polynomial" (c'est la machine déterministe qui est polynomial, pas l'oracle). Je pense que c'est ce que tu voulais dire mais que tu t'es mal exprimé.
Pour finir, il existe en théorie des machines de turing non déterministe. Elles sont basé sur "l'ordinateur à ADN", c'est a dire qu'on modelise le probleme sous forme ADN, on met tout dans une grosse bassine et on recupere le résultat (en temps polynomial). Le problème, c'est que si c'est en temps polynomial, ca semble etre en espace exponentiel, ce qui arrange pas vraiment le probleme (et gerer des tonnes d'ADN, c'est pas vraiment réaliste...).