Dialogue sur P vs NP (7)

Le dialogue avec Passe-Science, l'auteur de la vidéo P vs NP :

https://www.youtube.com/watch?v=8TrIW-4kfRg

Yu ：

Le problème P vs NP consiste à demander si NP = P? en réalité, c’est de demander si NP-complete = P? Dans ce cas, le problème P vs NP se concentre sur NP-complete.

Puisqu’on trouve qu’il est difficile de reconnaître NP-complete, on a déplacé le focus de NP-complete à NP :

Définition 1: NP est le problème décidable en temps polynomial sur une machine de Turing non-non-déterministe.

Définition 2: NP est un problème vérifiable en temps polynomial sur une machine de Turing.

NP est ainsi défini formellement. Au point de vue de la "forme", NP contient normalement P et NP-complete：

Mais au point de vue du "fond", ce n’est pas le cas. Puisque les attributs de NP comme « vérifiable et décidable » sont également partagés par P, de tels attributs ne pourraient pas être des attributs spécifiques de NP-complete, car NP-complete est quelque chose de nouveau, et ses attributs spécifiques n'ont pas encore été exprimés de manière formelle. En d'autres termes, ils ont disparu de NP. 

Par conséquent, NP-complete devient quelque chose comme une "boîte noire" dans NP, et la recherche de NP-complete dans NP devient une mission impossible. Tout comme si je cherche Toto dans un immeuble, et vous me dites que Toto est le voisin de Titi, mais je ne connais pas du tout Titi, il serait donc impossible de trouver Toto pour moi !

Dans ce sens, on pourrait questionner si la recherche de NP-complete dans NP (NP = P?) est comme si « les aveugles touchent un éléphant », . . .

Passe-Science ：

Je répond point par point:

"Le problème P vs NP consiste à demander si NP = P? en réalité, c’est de demander si NP-complete = P?"

Mathématiquement ça revient au même, P est différent de NP si et seulement si P est différent de NP-complet.

"car NP-complete est quelque chose de nouveau, et ses attributs spécifiques n'ont pas encore été exprimés de manière formelle"

Si ils le sont (exprimés formellement), les attributs spécifiques d'un problème NP-complet c'est précisément de pouvoir universellement exprimer n’importe quel autre problème pris dans NP. Pour être un problème NP-complet il faut qu'on puisse transformer en vous, en temps polynomial, un autre problème pris dans NP et n'importe lequel. C'est un attribut spécifique fort qui définit de manière formelle et précise l'ensemble dont on parle.

J'ajoute bien sur qu'à ce stade on ne pourra jamais fournir d'attributs qu'on puisse démontrer strictement spécifiques puisqu'on a pas

 résolu la conjecture, et que si la réalité est que P=NP alors P=NP=NP-complet et donc il n'y aura jamais aucun critère pour les départager, dans cet éventualité il n'existerait pas d'attributs spécifiques.

Mais pour le moment l'inverse est vrai aussi, l'attribut spécifique que je vous ai décrit ci dessus, vous ne pouvez pas non plus me démontrer qu'il n'est pas spécifique à NP-complet, si vous pouviez vous auriez résolu la conjecture.

Dialogue sur P vs NP (6)

Le dialogue avec Passe-Science, l'auteur de la vidéo P vs NP :

https://www.youtube.com/watch?v=8TrIW-4kfRg

Yu Li : Je suis d’accord, « Si on a P différent de NP alors on aurait bien disjonction entre P et NP-Complet.  

Le problème est que, les objets sont désignés et reconnus par des concepts, et le concept est formé par la définition dont la connotation consiste des attributs qui représentent l’essence des objets. Par conséquent, un objet désigné par un concept ainsi que sa reconnaissance dépend de la définition du concept.

Puisque les attributs comme « vérifiable » et « décidable » dans Définition 1 et Définition 2 sont partagés par les problèmes P, ils ne peuvent pas capturer l’essence du « vrai NP », autrement dit, « NP » désigné par Définition 1 ou Définition 2 peut-être n’est pas le « vrai NP », alors comment peut-on trouver NP different de P à travers ce « NP »?

C’est pour ça que je questionne sur la definition de « NP », …

Passe-Science : En fait je pense que surtout que la definition ne convient pas à ce que toi tu aimerais qu'elle désigne, mais c'est subjectif.  Rien empêche de définir ce qu'est un chat, et de définir ensuite ce qu'est un animal, meme si on sait qu'être un chat impliquera être un animal. Je ne dirais pas qu'il y a un "problème" dans la definition d'animal, c'est juste une classe plus large. Et il est légitime ensuite de se demander s'il existe d'autres animaux que des chats, ou d'autres NP que des P. 

La definition que tu aimerais être celle de NP me semble être celle de NP-complet, c'est juste qu'a mon avis tu veux faire coller ton "concept" dans la definition NP alors que ton concept semble plutôt être celui de NP-complétude. Mais il sera impossible de définir NP-complet d'une manière qui montrerait clairement qu'on a autre chose que P puisque ca serait répondre à la conjecture pour le moment irrésolue. 

Si on démontre un jour P different de NP, alors a mon avis, la definition que tu cherches c'est juste NP-complet. C'est a dire les "rapidement vérifiables et non trivialement décidables" (dans ce cas la ou P different de NP)

Des nuages dans chaque papier

Aujourd’hui, c’est l’anniversaire de ma fille Lise, son prénom chinois est 诗云 (poet, nuage).

Actuellement elle fait un stage au sud dans une entreprise médicale, le but de ce stage est de tester la qualité des papiers d’emballages médicaux.

J’ai adapté un poème de Thich Nhat Hanh où il parle du papier, le poème et le nuage :

1. Version en français 

Des nuages dans chaque papier

Si tu es poète, tu verras clairement que

Il y a un nuage flottant au-dessus cette feuille de papier.

Sans nuage, il n'y aura pas de pluie;

Sans pluie, les arbres ne peuvent pas pousser;

Et sans arbres, nous ne pouvons pas faire de papier.

Le cloud est essentiel pour que le papier existe.

Si le nuage n'est pas là, la feuille de papier ne peut pas être là non plus…

«Interbeing» est un mot qui n'est pas encore dans le dictionnaire, 

mais si nous combinons le préfixe «inter» avec le verbe «être», nous avons un nouveau verbe, inter-être.

Sans nuage, nous ne pouvons pas avoir de papier, 

nous pouvons donc dire que le nuage et la feuille de papier sont interdépendants

«Interbeing» est donc le Yin/Yang, …

2. Version en chinois

每张纸上都有一朵云 

如果你是诗人，你会清楚地看到

这张纸上漂浮着一朵云。

没有云，天就不下雨。

没有雨，树就不生长。

没有树，就不能造纸。

云于纸的存在至关重要。

如果云不在，纸也不能在……

«interbeing»不在词典里，

没有云，就没有纸，

所以可以说云与纸是«interbeing»，

是阴阳变易。

3. Version en anglais

Clouds in Each Paper

If you are a poet, you will see clearly that 

There is a cloud floating in this sheet of paper.

Without a cloud, there will be no rain;

Without rain, the trees cannot grow;

And without trees, we cannot make paper.

The cloud is essential for the paper to exist.

If the cloud is not here, the sheet of paper cannot be here either …

« interbeing » is a word that is not in the dictionary yet, 

but if we combine the prefix « inter » with the verb « to be », 

we have a new verb, inter-be. 

Without a cloud, we cannot have paper, 

so we can say that the cloud and the sheet of paper inter-are …

- Thich Nhat Hanh

Dialogue sur P vs NP (5)

Le dialogue avec Passe-Science, l'auteur de la vidéo P vs NP :

https://www.youtube.com/watch?v=8TrIW-4kfRg

Yu Li : Merci beaucoup de votre patience !

C’est vrai que le mot «imaginaire» que j’ai utilisé pour désigner cette NDTM (Non-Deterministic Turing Machine) “un peu subtile”, est susceptible d’avoir l’ambiguïté. En fait il existe en général trois interprétations de NDTM :

NDTM est une machine dotée d’une capacité de parallélisme infini ;

NDTM peut être simulé avec TM en temps exponentiel;

NDTM est une machine dotée de l’Oracle (dans le fameux article en 1971 de Cook).

Donc, ce serait mieux de mettre de côté « Définition 1 » basée sur cette subtile NDTM pour l’instant, et rester encore un peu sur « Définition 2 ».

En sens commun, NP et P sont différents, mais "Définition 2" dit : NP est une classe de problèmes vérifiables en temps polynomial par TM. Comme un problème P est également vérifiable en temps polynomial par TM, donc NP inclut P.

On remarque que, la relation entre NP et P est passée de l’« opposition » à la « inclusion ». C’est pour ça que je demande : y a-t-il un problème avec cette définition de NP ?

J’essaye d’expliquer ma question à travers une analogie :

Je connaissait le «vache», mais pas le «cheval». Un jour je voyait un troupeau de vaches et un troupeau de chevaux ensemble dans une herbe :

Yu demandait à Passe-Science : qu'est-ce que c’est ?

Passe-Science : c'est le cheval.

Yu : qu'est-ce qu'un cheval ?

Passe-Science : un cheval est un animal ayant une couleur.

Maintenant si vous me demandiez : tu sais ce que c’est un cheval ? 

Je ne peux que répondre: je ne sais pas, car une vache est aussi un animal ayant une couleur.

Passe-Science : Ha mais je comprend mieux ou se trouve la confusion, c'est complètement admis que P soit inclus dans NP par définition. Et par construction ça a toujours été le cas, et ce quelque soit la définition.

Que ça soit selon la définition 1 ou la définition 2 P est inclus dans NP. Si un problème est P c'est trivial qu'il peut aussi être résolu en temps polynomial sur une machine de Turing non-déterministe (définition 1, et qu'il est donc aussi NP) et c'est aussi trivial qu'il est vérifiable en temps polynomial (définition 2, et est donc aussi dans NP). Il n'y a jamais eu "d'opposition" qq soit la définition, rien n'a jamais tenter de définir NP comme un ensemble disjoint de P, ça a toujours été une relation d'inclusion et ce qu'on cherche à savoir c'est si cette inclusion est stricte ou si c'est en fait une égalité, s'il existe le moindre élément dans NP qui ne soit pas dans P. Le cote disjoint ça serait plutôt pour la classe NP-complet, mais évidemment on en est pas certain (puisque c'est toute la question) NP-complet ce sont les problèmes qui sont dans NP et aussi en qq sorte "maximalement dur" ou "au moins aussi dur que". Si on a P différent de NP alors on aurait bien disjonction entre P et NP-Complet. 

Voir la vidéo à partir de 9:35 je montre les inclusions avec des patatoïdes.

Dialogue sur P vs NP (4)

Le dialogue avec Passe-Science, l'auteur de la vidéo P vs NP :

https://www.youtube.com/watch?v=8TrIW-4kfRg

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?

Dialogue sur P vs NP (3)

Le dialogue avec Passe-Science, l'auteur de la vidéo P vs NP :

https://www.youtube.com/watch?v=8TrIW-4kfRg

Yu Li : Merci beaucoup de votre explication claire! J’ai une question :

Vous donnez 3 exemples des problems NP : le problème de 3-coloration, le problème du sac à dos, le problème SAT.

En sens commun, on sait bien que NP et P sont différents, car au contraire à P, on n’a que des algorithmes exacts du type de la recherche par force brute en temps exponentiel, ou des algorithmes approchés en temps polynomial pour résoudre les problèmes NP.

Pourtant si un problème NP est défini comme un problème dont la solution peut être rapidement vérifiable, alors un problème P est aussi rapidement vérifiable.

Dans ce cas, comment peut cette propriété capturer la nature de NP qui est sensé être différent de P ?

Passe-Science : Bonjour! merci pour votre intérêt dans cette vidéo. Je ne suis pas totalement certains d'avoir saisi votre question mais je pense que je vois.

En gros vous vous demandez comment on peut RIGOUREUSEMENT définir la classe NP et définir la classe P sans avoir à l'avance de critère pour séparer les deux notions. (et sans se reposer sur l'intuition qui ne donne pas de rigueur formelle)

Alors déjà, lorsqu'on rentre dans le cadre rigoureux, on n’étudie ici que les problèmes dit de "décision" c'est à dire formulé sous une forme ou la réponse est oui ou non.

par exemple "puis je colorier ce graphe avec 3 couleurs?" (plutôt que de demander comment le faire à l'algorithme). Parmi tous les problèmes de décision, on définit 2 ensembles:

Classe P: les problèmes tels qu'il existe un algorithme codable sur une machine de Turing universelle (Ça c'est la formalisation rigoureuse d'un ordinateur) répondant à la question en complexité polynomiale.

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.

C'est un peu subtile la définition rigoureuse de cette seconde chose mais, en gros, ç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. Donc on a bien 2 définitions rigoureuses, différentes, pour définir les deux classes, mais il se peut que ces définitions, bien que distincte, définissent un objet unique (si P=NP).

Ensuite il y a la classe NP-complet qui est une surprise: on peut démontrer qu'il existe parmi la classe NP des problèmes particuliers tels qu'on puisse y ramener n'importe quel autre

problème NP en temps polynomial. Ce n'est pas du tout évident au départ que la classe NP-complet n'est pas vide, c'est le Cook-Levin theorem qui donne le premier exemple de problème NP-complet.

Ensuite une fois qu'on a cet exemple, c'est beaucoup plus simple après pour démontrer que d'autres problèmes sont NP-complets, il suffit de montrer qu'on peut les transformer en cet exemple precis, ou en d'autres problèmes qu'on a déjà transformer dans cet exemple. (ça c'est ce que je fais dans la vidéo).

Ne pas hésiter à préciser votre question si je n'y ai pas répondu.

Dialogue sur P vs NP (2)

Maintenant, je reviens au P vs NP problème.

En termes courants, P (Polynomial) désigne une classe de problèmes faciles à résoudre par l’ordinateur, c'est-à-dire qu'il existe un algorithme en temps polynomial, comme la recherche du plus court chemin entre deux endroits dans le GPS.

NP (Non-deterministic Polynomial) désigne une classe de problèmes difficiles résoudre par l’ordinateur, tels que les trois exemples dans la vidéo 【1】: le problème de 3-coloration, le problème du sac à dos, le problème SAT. 

Jusqu’à présent, on n’a que des algorithmes exacts du type de la recherche par force brute en temps exponentiel, ou des algorithmes approchés en temps polynomial.

En sens commun, on sait bien que NP et P sont différents, mais lorsqu’on souhaite d’avoir une compréhension plus poussée sur NP, la théorie en informatique dit : 

• Un problème dans NP est un problème dont la solution peut être rapidement vérifiable.

• Lorsqu’une solution à un problème est rapidement vérifiable (NP), peut-elle être rapidement trouvée?

Par exemple pour le problème 3-coloration, en tant donné une coloration du graphe, cette coloration peut rapidement être vérifiée si deux noeuds adjacents sont colorés de la même couleur.

Bien entendu, P est également rapidement vérifiable。 Maintenant le fameux problème P vs NP est posé ainsi 【2】:

Comment pensez-vous de cette question, c’est-à-dire, la façon de poser la question?

Référence:

【1】https://www.youtube.com/watch?v=8TrIW-4kfRg

【2】May 2, 2013 (The New Yorker)，A Most Profound Math Problem， Alexander Nazaryan, http://www.newyorker.com/tech/elements/a-most-profound-math-problem

Dialogue sur P vs NP (1)

Récemment, Didier, Louis et moi, nous commençons à discuter sur le problème P vs NP que j’ai étudié depuis 10 ans, … 

Louis :  Pourrais-tu un jour m'éclairer sur ce problème P vs NP ? J'avoue n'y rien comprendre.

Didier : Peut-etre cette vidéo :

https://www.youtube.com/watch?v=8TrIW-4kfRg

Yu : Cette vidéo est super! Mais je questionne si ce qu’il a expliqué clairement avec la logique et le mathematics n'est pas un problème mal posé, …

Le problème P vs NP a été formalisé par Cook en 1971.  Ce problème est informellement présenté comme la vidéo explique :  

- Lorsqu’une solution à un problème est rapidement vérifiable (NP), peut-elle être rapidement trouvée (P)?

Depuis lors, beaucoup des efforts ont été consacrées à la résolution  de ce problème jusqu’à présent, mais il reste encore un des 7 « milleniums problems » sans résultat intéressant, …

J’essaye d’expliquer mon opinion à travers une analogie :

Yu connaissait le «vache», mais pas le «cheval». Un jour, elle est venue en France et voyait un troupeau de vaches et un troupeau de chevaux ensemble dans une herbe.

Yu (montrant les chevaux) a demandé Louis : qu'est-ce que c'est?

Louis : c'est le cheval.

Yu : qu'est-ce qu'un cheval?

Louis : un cheval est un animal ayant une couleur.

Si Louis continue à demander à Yu : est-ce que maintenant tu sais ce que c’est un cheval? 

Que peut répondre Yu? Que pensez-vous de ce dialogue?

Référence :

【1】May 2, 2013 (The New Yorker)，A Most Profound Math Problem， Alexander Nazaryan :http://www.newyorker.com/tech/elements/a-most-profound-math-problem

【2】La traduction de l’article 【1】en chinois par Yu Li ：http://blog.sciencenet.cn/blog-2322490-995211.html

Les Habits neufs de l’empereur

Dans la crise actuelle, la revision du conte d'Hans Christian Andersen (1805-1875), les «nouveaux vêtements de l’empereur», pourrait encore nous inspirer, . . .

Il y a de longues années vivait un empereur qui aimait par-dessus tout être bien habillé. Il avait un habit pour chaque heure du jour.

Un beau jour, deux escrocs arrivèrent dans la grande ville de l’empereur. Ils prétendirent savoir tisser une étoffe que seules les personnes sottes ou incapables dans leurs fonctions ne pouvaient pas voir et proposèrent au souverain de lui en confectionner un habit. L’empereur pensa qu'il serait exceptionnel et qu’il pourrait ainsi repérer les personnes intelligentes de son royaume. Les deux charlatans se mirent alors au travail.

Quelques jours plus tard, l’empereur, curieux, vint voir où en était le tissage de ce fameux tissu. Il ne vit rien car il n’y avait rien. Troublé, il décida de n’en parler à personne, car personne ne voulait d’un empereur sot.

Il envoya plusieurs ministres inspecter l’avancement des travaux. Ils ne virent pas plus que le souverain, mais n’osèrent pas non plus l’avouer, de peur de paraître imbéciles.

Tout le royaume parlait de cette étoffe extraordinaire. Le jour où les deux escrocs décidèrent que l’habit était achevé, ils aidèrent l’empereur à l’enfiler.

Ainsi « vêtu » et accompagné de ses ministres, le souverain se présenta à son peuple qui, lui aussi, prétendit voir et admirer ses vêtements.

Seul un petit garçon osa dire la vérité : “Le roi est nu ! ”. 

Référence :

https://fr.wikipedia.org/wiki/Les_Habits_neufs_de_l%27empereur