Le dialogue avec Passe-Science, l'auteur de la vidéo P vs NP :
Yu Li : Merci beaucoup pour votre réponse rapide et patiente!
Oui, j’attends à une définition formelle de NP qui soit cohérente avec le sens en commun :
« Il n’y a pas d’autres voies qui s’offrent aux hommes, pour arriver à une connaissance certaine de la vérité, que l’intuition évidente et la déduction nécessaire ». - Descartes
Vous expliquez :
Classe NP: pour non-deterministic polynomial, qui en gros se demande s'il existe un algorithme finissant en temps polynomial sur une machine de Turing non déterministe. (Noter Définition 1)
Le problème est qu’ici, la « machine de Turing non-déterministe » n'existe pas dans notre monde physique à ce jour ! Comme vous dites « ça revient à doter la machine, d'une capacité de parallélisme infini, ce qui en forme vulgarisée revient à lui donner la possibilité de tester toutes les solutions en même temps ». En plus, cette « machine » fait référence à « Oracle » dans le théorème de Cook (voir son fameux article en 1971 ).
En fait, la définition informelle de NP (dont la solution peut être rapidement vérifiable) peut aussi être formalisée :
- NP est une classe des problèmes vérifiables en temps polynomial par une machine de Turing. (Noter Définition 2)
Il semble que ces deux définitions sont différentes de leur essence :
Définition 1 sépare NP de P, mais elle est basée sur la « machine de Turing non-déterministe » imaginaire, tandis que Définition 2 est basée sur la « machine de Turing » réelle, mais elle confond NP avec P.
En sens commun, bien que des différentes définitions d’un objet peuvent avoir le degré d'abstraction et le mode d’expression différente, mais elles devraient avoir la cohérence, c’est-à-dire, elles devraient désigner le même objet.
Donc, mes questions sont:
1. Y a-t-il un problème avec les définitions de NP ?
2. La définition de NP est-elle liée aux difficultés pour comprendre le problème P vs NP (dans votre vidéo, beaucoup de gens expriment ce sentiment) ?
Passe-Science : Bonjour, vous dites:
"Définition 1 sépare NP de P, mais elle est basée sur la « machine de Turing non-déterministe » imaginaire, tandis que Définition 2 est basée sur la « machine de Turing » réelle, mais elle confond NP avec P. »
Déjà je pourrais revenir sur cette remarque parlant d'imaginaire qui est un peu douteuse car toutes les mathématiques sont des modèles abstraits, même le chiffre 1, et une machine de Turing déterministe est autant un modèle abstrait qu'une machine de Turing non déterministe.
Parler même de complexité algorithmique c'est par définition un comportement à l'infini et c'est donc aussi un modèle abstrait, etc... Mais c’était juste pour la remarque, je ne vais pas trop digresser sur le sens ou l'absence de sens à déclarer que certains modèles mathématiques sont réels et d'autres non.
Il y a ici plus court, pour réagir à votre paragraphe, il y a une confusion entre plusieurs choses.
-1) Le problème de décision dans son intégralité, exemple "trouver la procédure pour répondre, quelque soit le graphe, à la question se demandant si chaque graphe est 3-coloriable ou non" On est au niveau dans l'ensemble infini des instances possibles de notre problème et c'est à ce niveau la qu'on peut parler de complexité algorithmique.
-2) Se poser la question au niveau d'une instance de ce problème, c'est a dire ici pour un graphe donné. "Le graphe G est il 3-coloriable?"
-3) Se poser la question pour une instance donnée et un candidat solution donné. Exemple: "La 3-coloration suivante "C" est elle une 3-coloration valide pour le graphe G?" Et si on veut parler de complexité dans ce cas 3 on va raisonner sur l'ensemble des instances graphe+candidat-coloration possibles.
Et si on prend votre définition 2 pour NP, elle n'est en aucun cas la même que la définition de la classe P. Car elle ne porte pas sur le même niveau.
La classe P c'est l'ensemble des problème de décision qui peuvent être RÉSOLUS en temps polynomial (c'est à dire qu'on ne fourni à l'algorithme que l'instance du problème, ici un graphe G, et il doit répondre en temps polynomial à la question est il 3-coloriable)
La classe NP c'est l'ensemble des problèmes de décision qui peuvent être VÉRIFIÉS en temps polynomial. (et non résolus, c'est à dire qu'on fournit à l'algorithme une instance du problème, comme un graphe donné, ET un candidat solution. Le travail de l'algorithme est juste de se prononcer sur la validité du 3-coloriage fourni et non de conclure sur la 3-coloriabilite du graphe donné, qui pourrait être 3-coloriable d'une autre manière si le candidat coloriage ne convient pas).
Donc pour la classe P et la classe NP il y a bien une notion de complexité polynomiale dans les deux cas, mais pas pour réaliser la même chose.
Vous dite "Définition 1 sépare NP de P". Les définitions 1 et 2 sont mathématiquement équivalentes, donc si la définition semble "séparer" qq chose (ou qq soit votre conclusion a propos de la définition 1) alors la définition 2 fait la même chose. La définition 1 c'est une formulation en terme de RÉSOLUTION en temps polynomial sur une machine de Turing non déterministe, la définition 2 c'est une formulation en terme de VERIFIABILITE en temps polynomial sur une machine de Turing déterministe. Et comme je le présente ci dessus, ce n'est pas le même travail qui est qualifié de polynomial dans un cas comme dans l’autre.
C'est plus clair?
Aucun commentaire:
Enregistrer un commentaire