Yu : Je répond aussi 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.
Mais en matière de contenu, "NP = P? » désigne à la recherche du problème NP-complet dans NP, et comme NP-complet équivaut à une "boîte noire" dans NP, il est en réalité introuvable.
"NP-complete = P?", par exemple, peut signifier à la recherche de la racine du problème NP-complet et la relation intrinsèque entre NP-complet et P, qui serait une direction de recherche complètement différente, . . .
Par conséquent, mathématiquement ça revient au même, mais en réalité ce n’est pas le cas.
- 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.
Formellement, cette définition basée sur la "réduction" définit "de manière formelle et précise" NP-complet; mais étant donné un problème quelconque, il est impossible de déterminer de manière déterministe si ce problème appartient à NP-complet, car il n'existe pas d'algorithmes généraux qui réduisent le problème SAT à ce problème. Par exemple, la réduction du problème SAT au problème de 3-coloration dans votre vidéo n'est qu'une « heuristique ».
Par conséquent, il faut déterminer si la définition de NP-complet définit de manière formelle et précise l'ensemble dont on parle, . . .
En résume, je questionne :
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 ?
Didier : J'ai aussi le sentiment que les difficultés de discussions sur le thème P ?=? NP viennent des outils intellectuels du monde occidental.
La première difficulté vient de la construction des mots : sans base idéographique, sans connaissance des clefs de leur construction (apprentissage du grec et du latin), je communique en espérant mais la plupart du temps en croyant que, pour chaque mot, mon interlocuteur désigne la même chose que moi.
Ici, les "machines" ont déjà des définitions variables ... avec le summum, l'Oracle ! je vais demander à ma petite fille qui manipule le mot Licorne et qui a l'air assez proche.
La seconde difficulté vient de la modélisation, formidable outil de la réussite industrielle du monde occidental : en sciences expérimentales, l'étude de phénomènes réels conduit à proposer un ou plusieurs modèles théoriques; la manipulation de ces modèles facilite les recherches; enfin, les résultats théoriques doivent être confrontés à la réalité, ce qui permet de valider/écarter certains modèles; et ainsi de suite, s'enrichissent nos connaissances.
Ce processus de va-et-vient (Tiens, tiens ! le Yin-Yang au cœur de l'Occident ?) est extrêmement productif. Malheureusement, par commodités, par suffisance, par mode peut-être aussi, nous omettons de procéder à la phase indispensable de validation du modèle par confrontation au réel : quelque fois, nous allons jusqu'à confondre le modèle et la réalité. Notre époque aime tout modéliser (jusqu'à nos comportement humains! n'est ce pas, les GAFAs ?), adore conceptualiser, voue aux nues la science pure que seraient les mathématiques, et se régale dans l'art (si) conceptuel (qu'on y comprend rien au point qu'il remplace la religion).
Ici, le point de départ est l’ordinateur et les problèmes qu'il peut résoudre par programme en temps raisonnable. Un de ses modèles est la machine de Turing. La manipulation théorique de ce modèle conduit à la version non-déterministe ou encore à la machine avec oracle. A partir de là, il faudrait revenir au monde physique : confronter ces modèles avec le monde informatique aujourd'hui. (A quoi sert de réfléchir à des problèmes soi-disant solvables avec des machines ... inexistantes ?)
La troisième difficulté réside dans notre grammaire et/ou notre logique (y a t'il une différence ?) : notre discours pour expliquer quelque chose ressemble à une démonstration. Il ne laisse pas la place à l'intelligence de l'interlocuteur : bien construit, c'est une suite d'arguments et déductions qui vise la complétude. L'interlocuteur est prisonnier de l'argumentaire alors que, dans l'équivalent chinois, il devient acteur : le discours est incomplet de telle sorte que le destinataire est amené à refaire lui-même une partie des raisonnements/déductions (c'est ce qu'on est sensé faire quand on enseigne). Le danger du discours se trouve dans l'introduction invisible d'un argument faussé ou d'un glissement de sens des mots (surtout si l'on a affaire avec un concept) : l'apparence logique de l'exposé et l’enchaînement ininterrompu argument-déduction ne laissent pas de temps pour une analyse critique de chacune des phrases. Beau discours, mais conclusion ... peut-être incertaine.
Ici, la résolution parallèle du programme non-déterministe, la mesure du temps égale pour 1 action déterministe avec plusieurs actions non-déterministe, l'introduction de l'oracle dont aucune définition n'est fournie, sont autant de distorsions introduites dans le discours.
La quatrième difficulté concerne le langage, ou plutôt ses limites. Le langage s'avère fort pratique, voire même indispensable, à chaque instant du jour, pour traiter des problèmes communs du monde que je perçois. Mais si je commence à vouloir explorer les limites de ce monde, je suis conduit à parler un méta-langage : Dieu, l'Essence, l'Universel, l'Infini .... et quand on fini par mélanger ce méta-langage avec le langage, on arrive à ne plus rien distinguer de ce monde et de son au-delà.
Ici, au début, on parle d'ordinateurs et de programmes (quoi de plus terre à terre !) et puis, on utilise le langage mathématique pour décrire le fonctionnement de l'ordinateur et des programmes. Mais quand ça commence à coincer, on introduit l'oracle hors du langage mathématique (et on arrive au Ciel !)
Yu：NDTM a été proposé pour définir NP formellement par Cook dans son fameux article en 1971.
J’extraire quelques paragraphes [1] :
- Theorem 1. If a set S of strings is accepted by some nondeterministic Turing machine within polynomial time, then S is P-reducible to {DNF tautologies}.
(Ici, S correspond à NP, {DNF tautologies} est équivalent au SAT problème.)
In order to make this notion precise, we introduce query machines, which are like Turing machines with oracles in [1].
A query machine is a multitape Turing machine with a distinguished tape called the query tape, and three distinguished states called the query state, yes state, and no state, respectively. If M is a query machine and T is a set of strings, then a T -computation of M is a computation of M in which initially M is in the initial state and has an input string w on its input tape, and each time M assumes the query state there is a string u on the query tape, and the next state M assumes is the yes state if u ∈ T and the no state if u ∈/ T . We think of an “oracle”, which knows T , placing M in the yes state or no state.
Référence :
[1] Stephan Cook, The Complexity of Theorem-Proving Procedures, 1971:
