Résoudre P vs NP à partir de considérations de base I. La présupposition d’une similarité entre procédure de solution et de vérification

Voici, traduite en français, la définition de la conjecture « P vs NP » telle qu’on la trouve sur Wikipédia en anglais. Partons de la version en anglais car la définition de l’entrée en français est d’emblée assez alambiquée :

« Le problème P vs NP est un problème majeur non résolu en informatique. Il s’agit de savoir si tout problème dont la solution peut être vérifiée rapidement peut également être résolu rapidement. »

Examinons quelques exemples de problèmes dans cette perspective d’une comparaison entre vitesse de résolution et vitesse de confirmation que le problème a bien été résolu.

Premier cas : ce genre de casse-tête où l’on vous propose deux pièces de métal imbriquées en vous mettant au défi de les séparer.

Si vous êtes paresseux, ou avez jeté l’éponge au bout d’un moment, vous trouverez la solution sur le mode d’emploi qui accompagne le jeu. Comme il vous est montré, celle-ci consiste en une ou plusieurs rotations des pièces l’une par rapport à l’autre suivie d’un alignement très particulier permettant de les désemboîter.

Ce sont de petits dessins qui vous permettent de saisir aisément les manipulations ad hoc. S’il fallait cependant décrire entièrement l’opération sans recourir à une aide visuelle, une telle description exigerait dans la plupart des cas, un nombre considérable de phrases.

Par contre, vérifier que le problème a bien été résolu ne requiert qu’un examen visuel d’une fraction de seconde : il suffit de constater que les deux pièces ont effectivement été séparées.

Second cas : celui d’un puzzle.

Décrire une procédure de solution pourrait débuter de la manière suivante :

« Mettre à part les pièces ayant un bord plat.

Parmi les pièces ayant un bord plat, les séparer en deux groupes : les pièces à tenons et les pièces à mortaises.

Prendre une pièce d’un des deux groupes et chercher grâce à la similarité de couleur une pièce de l’autre groupe à laquelle elle pourrait s’emboîter.

Répéter jusqu’à épuisement des pièces à bord plat. Se tourner ensuite vers les autres pièces.

Etc. »

Vérifier que le problème est bien résolu ne requiert dans ce cas aussi qu’un examen visuel d’une fraction de seconde : il suffit d’observer qu’il n’existe pas de trou dans l’image reproduisant celle du couvercle de la boîte du puzzle dont on se demande s’il est effectivement terminé. Tout cela est extrêmement banal : vérifier que le problème posé a bien été résolu est quasi instantané, et sans commune mesure avec la difficulté à le faire.

Donc si « La conjecture P vs NP consiste à savoir si tout problème dont la solution peut être vérifiée rapidement peut également être résolu rapidement », les deux exemples du casse-tête et du puzzle montrent clairement qu’il existe des problèmes dont la solution peut être vérifiée rapidement sans qu’ils puissent être résolus rapidement.

Mieux, les deux exemples choisis suggèrent fortement qu’il n’existe aucun lien entre la difficulté du problème et celle de la vérification qu’il a bien été résolu.

Ce qui ne peut signifier qu’une seule chose : que la définition de P vs NP dont nous sommes partis n’est pas la bonne, la réponse étant trop évidente si on la prenait à la lettre, et n’aurait certainement pas mobilisé une génération de mathématiciens. Il faut donc aborder et examiner P vs NP autrement.

La définition de P vs NP du Clay Mathematical Institute

Abordons les choses autrement : partons du texte du Clay Mathematical Institute qui offre un prix d’un million de dollars pour la solution de la conjecture P vs NP. Elle y est caractérisée de manière intuitive, à entendre par opposition à de manière formelle, c’est-à-dire « avec des équations ».

Sur le site du Clay Mathematical Institute : « Imaginons que vous deviez organiser le logement d’un groupe de quatre cents étudiants. Les places sont limitées et seuls cent étudiants pourront être accueillis au foyer. Pour compliquer les choses, le doyen vous a fourni une liste de paires d’étudiants jugés incompatibles et a demandé qu’aucune paire de cette liste ne figure dans votre choix final.

Il s’agit d’un exemple de ce que les informaticiens appellent un problème NP, puisqu’il est facile de vérifier si un choix donné de cent étudiants proposé par un collègue satisfait aux critères (à savoir qu’aucune paire présente dans la liste de votre collègue n’apparaisse également dans la liste du bureau du doyen), mais la tâche consistant à générer une telle liste à partir de rien (from scratch) semble si difficile qu’elle est totalement irréalisable. En effet, le nombre total de façons de choisir cent étudiants parmi les quatre cents candidats est supérieur au nombre d’atomes dans l’univers connu ! Ainsi, aucune civilisation future ne pourra jamais espérer construire un superordinateur capable de résoudre le problème par la force brute, c’est-à-dire en vérifiant toutes les combinaisons possibles de 100 étudiants.

Toutefois, cette difficulté apparente ne reflète peut-être que le manque d’ingéniosité de votre programmeur. En fait, l’un des problèmes majeurs de l’informatique est de déterminer s’il existe des questions dont la réponse peut être rapidement vérifiée, mais dont la résolution par une procédure directe est extrêmement longue. Des problèmes tels que celui invoqué ci-dessus semblent certainement être de ce type, mais jusqu’à présent, personne n’a réussi à prouver que l’un d’entre eux est vraiment aussi difficile qu’il n’y paraît, c’est-à-dire qu’il n’existe pas de moyen réalisable de générer une réponse à l’aide d’un ordinateur. Stephen Cook et Leonid Levin ont formulé indépendamment en 1971 le problème P (c’est-à-dire facile à trouver) versus NP (c’est-à-dire facile à vérifier). »

Reprenons la question à partir de cette caractérisation du problème, « P » signifiant facile à résoudre vs « NP » voulant dire facile à vérifier, dans le cas particulier présenté : comment organiser l’hébergement de 400 étudiants dont seuls 100 en réalité peuvent être accueillis, assorti d’une contrainte : ne pas mettre dans la même chambre deux personnes incompatibles dont la liste a été établie par ailleurs. Il nous est dit qu’il y a là un exemple typique de problème non-P.

Quand Stephen Wolfram observe dans son A Project to Find the Fundamental Theory of Physics, qu’« il n’y a pas de méthode générale de raccourcir la série d’étapes nécessaires pour dériver un théorème. En d’autres termes, il peut être arbitrairement difficile d’obtenir un résultat en mathématiques » (2020 : 558-59), il s’agit d’une considération du même type : la carte d’un désert peut être extrêmement petite par rapport à la surface du désert lui-même, alors que pour un paysage très accidenté, il n’est pas possible de dresser une carte fidèle beaucoup plus petite que le pays lui-même. Tout dépend du cas. Tout est là ! C’est de cela également qu’il s’agit, on le devine, avec P vs NP, d’une réticence, toute mathématicienne, à admettre que « tout dépende du cas », une caractéristique propre au monde qui nous entoure, mais heureusement absente en général du monde des mathématiciens.

Et, si c’est de cela qu’il s’agit, pourquoi les mathématiciens et les informaticiens ont-ils même voulu formuler cette conjecture P vs NP, de la relation entre problème P, facile à résoudre, et problème NP, c’est-à-dire facile à vérifier ? Uniquement sans doute parce que le problème que l’on choisit comme cas typique de P vs NP (cf. ci-dessus : le logement d’un certain nombre de personnes en excédent du nombre de logements disponibles, alors qu’existent des incompatibilités entre ces personnes) suggère une similarité entre la solution (un certain nombre d’opérations à faire) et la vérification (un certain nombre d’autres opérations à faire), alors que d’autres exemples de problèmes, comme ceux du casse-tête et du puzzle, ne suggèrent pas, voire excluent, qu’il existerait une quelconque similarité entre procédure de solution du problème et procédure de vérification qu’il a effectivement été résolu.

(à suivre…)

Partager :

26 réponses à “Résoudre P vs NP à partir de considérations de base I. La présupposition d’une similarité entre procédure de solution et de vérification”

  1. Avatar de Un Informatitien
    Un Informatitien

    La bonne manière d’établir la définition de P VS NP qui est vraiment déstabilisante et qui ne repose pas sur l’intuition humaine est de comparer les classes de problèmes entre les machines de Turing déterministes et les machines de Turing non-déterministe (voir ici : https://fr.wikipedia.org/wiki/Machine_de_Turing_non_déterministe).

    Comme souvent, en se limitant à la mathématique, tout est limpide et simple, c’est le besoin des humains d’expliquer intuitivement qui vient compliquer le problème. Même chose avec le quantique.

    1. Avatar de Paul Jorion

      Vous anticipez mon chapitre II. C’est de bonne guerre 😉 . Encore faut-il expliciter à quoi renvoie précisément la distinction entre machine de Turing déterministe et machine de Turing non-déterministe.

      Par exemple, peut-on dire qu’une machine de Turing non-déterministe existe de la même manière qu’existe une machine de Turing déterministe ?

      1. Avatar de Un Informatitien
        Un Informatitien

        Mais, ne resombrez-vous pas par cette question sur l’existence des machines non-déterministes dans les travers des humains qui veulent intuitivement expliquer certaine choses ?

        Je pense que la question n’est pas pertinente pour y voir une distinction entre P et NP. Cependant, si P est égal à NP, ces machines peuvent faire les mêmes calculs en temps polynomial. Et ça, c’est vachement contre intuitif 😉

        1. Avatar de Paul Jorion

          ne resombrez-vous pas par cette question sur l’existence des machines non-déterministes… Je pense que la question n’est pas pertinente pour y voir une distinction entre P et NP.

          Vous allez voir 😉 .

      2. Avatar de Garorock
        Garorock

        Une machine non-déterministe, serait- ce comme si ChatGPT devenait un « nouveau » Beaudelaire?

  2. Avatar de Khanard
    Khanard

    https://youtu.be/AgtOCNCejQ8

    une autre approche de cette théorie . Les deux se complètent et se retrouvent pour les néophytes que bon nombre d’entre nous sommes

    bonne soirée

    1. Avatar de Paul Jorion

      Je ne suis pas sûr de comprendre ce que vous voulez dire par « autre approche ».

      1. Avatar de Khanard
        Khanard

        Par « autre approche » je souhaitais simplement proposer une interprétation vulgarisée pour tous ceux qui comme moi ont du mal avec ces notions .

      2. Avatar de Paul Jorion

        Ok. J’ai regardé la vidéo jusqu’au bout, attendant une approche « alternative » de la question, or il s’agit d’un exposé clair et bien fait, mais des plus classiques.

        1. Avatar de Khanard
          Khanard

          Nous sommes d’accords alors . Mais j’attends avec impatience la suite de vos articles .

          cordialement

  3. Avatar de timiota
    timiota

    Compter le nombre de participants dans une manif semble être un problème « N » (non déterministe).

    Ceci dit puisqu’il y a dans la vidéo youtu.be/AgtOCNCejQ8 de Khanard-le-curieux la question du repliement des protéines (classée dans NP), il est bon de signaler que ce repliement a reçu une solution qui me semble « P », mais qui n’est pas 100% rigoureuse: c’est par Deep Learning, et on ne garantit pas qu’on est sur un minimum global mais seulement sur un minimum local du « paysage de potentiel », un minimum « plutôt sympa » et coïncidant bien avec la réalité, mais pas le truc thermodynamiquement béton.

    Je suppose que de la même façon qu’en maths on sait définir le « presque » (les cours de topologie, l’adhérence, le voisinage, les ensemble compact, le théorème de Bolzano-Weierstrass, et puis les convergences au sens de Lebesgue, les mesures « presque partout », les restrictions portant sur des « ensembles de mesure nulle ») , les algorithmiciens se ont rendus compte que la vie résolvait souvent des problèmes NP de façon rapide mais approximative, s’approchant beaucoup d’une solution idéale.
    Ce n’est pas la vie en rose, c’est Boole en gris et logique floue.

    1. Avatar de Ruiz
      Ruiz

      @timiota Y a t il vraiment une difficulté à compter les manifestants, à l’heure des drones et des téléphones portables localisables (cf Ukraine) ?
      Il y a des décomptes ou estimations publiés manifestements divergents, mais le sont-ils de façon totalement erratique et aléatoire ?
      Apparemment non, il y a un biais en fonction de l’idée que ce fait l’émetteur du chiffre du résultat à obtenir, plus grand ou plus faible.

      Prendre la racine carrée du produit des nombres extrèmes constitue un estimateur comme un autre …

      Le « presque » que la mathématique arrive à concevoir, est-il étranger à l’arithmétique, et de ce fait le théorême de Gödel qui ne s’appliquerait qu’à celle-ci, n’exprimerait-il qu’un principe d’incomplétude non universel ?

      1. Avatar de arkao

        @Ruiz
        Bien sûr qu’on peut compter facilement le nombre de manifestants. Il suffit de photographier le cortège à partir d’un drone et de publier en accès libre les clichés afin que chacun puisse faire le calcul.
        Comme l’utilisation des drones dans le ciel parisien est réglementé, ce serait à la préfecture de police d’effectuer cette tâche.
        Mais ça n’arrange personne d’avoir des chiffres exact.

      2. Avatar de arkao

        A défaut de photos en drone, une vidéo complète du parcours avec une caméra en haut d’une perche:
        https://www.youtube.com/watch?v=jKEMAJ3FNg4
        Avis aux amateurs de comptage 🙂

          1. Avatar de timiota
            timiota

            Oui, ben à vue de nez, ça ne dépasse par une personne par m², la densité moyenne de ces prises de vue.
            (Quelque part entre 2 et 3 par m², les foules commencent à avoir du mal à s’écouler, les risques d’incidents graves type piétinement de Séoul cet hiver augmentent et sont inévitables vers 3.5 à 4 /m² sur des surfaces un peu étendues, voir Bain et al. 2019, Science, sa thèse en ligne sur hal aussi : étude sur les départs de marathon massifs, une belle « hydrodynamique non-linéaire).

            Le Fg St Antoine fait 2200 m de long, environ 14 m de large (largeur effective, on voit que c’est pas toujours occupé jusqu’aux murs, compte tenu des mobiliers urbains et de la voirie etc.).
            Ca fait donc 30800 personnes quand c’est plein partout…. Quand je dis ça je me fais engueuler, le « ressenti » est à 80 000 voire 150 000, mais bon, c’est un ressenti.

            Il faut dire que quand on pense à Epidaure et son théâtre (rayon de 58m, un peu plus qu’un demi-cercle, et pourtant 14 000 places) on se dit que sur 2200 m il y a de la place, mais on n’est pas du tout aussi tassé que dans un théâtre à gradin, et puis la surface en rond, une fois développée est 1/6ème de la surface du Fg St Antoine.

            Je dis ça je dis rien…

            1. Avatar de arkao

              @timiota
              Merci.
              Pour le « ressenti », pas trop la peine d’en parler quand on est sur le terrain au raz des pâquerettes, comme Fabrice à Waterloo.
              Un de mes étalon est le festival de musique du Hellfest où le nombre d’entrées journalières est fixé à 60 000 personnes. Mais comme c’est statique et pas sur un linéaire pas évident de comparer.
              En tout cas qu’il y avait ce samedi moins de provinciaux venus en cars par rapport à la « marche contre la vie chère » du 16 octobre 2022. Entre guillemets car on se doute bien qu’il s’agissait surtout d’évaluer la motivation des troupes 😉

            2. Avatar de CloClo
              CloClo

              Salut Timiota,

              L’avantage quand tu dis rien c’est que tu dis exactement ça. Et ça c’est bien vu ! Le compte y est.

              Pour ta remarque plus haut sur NP et P et la fonction « presque » qui est la touche résolution rapide de la machine à calculs Univers, faut toujours s’en remettre à ça, crackage à haute densité, sous peine de rester coincé dans les limbes de l’enfer des mathématiques idéales… Je dis ça, je dis rien non plus.

    2. Avatar de Khanard
      Khanard

      @Timiota

      Moi? Curieux ? Non! Vous croyez ? Ah bon . Mais est ce un défaut ?

  4. Avatar de Ruiz
    Ruiz

    « rapidement » Comment introduire la notion de temps dans un problème de logique ?
    N’est-ce pas plutôt une notion de complexité, qui est abordable statiquement.

    Les deux examples intuitifs donnés « casse-tête » et puzzle renvoient à un contexte matériel respectivement 3D et 2D dont la vérification n’est « rapide » que parce qu’elle est visuelle.

    Pour une intelligence artificielle, ce n’est peut-être pas aussi évident, à voir la complexité des moyens employés pour assurer une vision et des algorithmes ou autres traitements nécessaires à assurer l’interprétation.

  5. Avatar de Timiota
    Timiota

    Oui c’est parce qu’il existe déjà un parallélisme pré câblé : celui du cortex visuel, avec juste quelques couches (non parallèles, récurrentes) pour la corrélation finale (ceci est une pipe).
    Mais en principe c’est juste un pré facteur dans les lois d’échelle P,NP…

    Et à l’envers, on s’émerveille de ChatGPT mais le langage est fabriqué par principe comme de la pensée laminée linéairement (métaphore de l’oignon extrudé chez PJ). L’exploit relatif de ChatGPT est de retraiter à l’aide de parallélisme « basique » (Réseaux neuro truc…) la production séquentielle des mots.

    Ce serait rigolo de voir ChatGPT discuter « à la française » : en s’interrompant avant la fin de la question posée etc. , signe d’une urgence à blatérer et donc d’une situation où il y a un bien un corps physique en couplage fort.

    1. Avatar de un lecteur
      un lecteur

      « avec juste quelques couches (non parallèles, récurrentes) pour la corrélation finale », par FFT c’est parallélisable. À la fin il ne reste que des diodes, sophistiqué mais des diodes…

      1. Avatar de timiota
        timiota

        L’optique est très adaptée à la parallélisation (de la FT notamment, qui devient « F » FT dans la foulée. Voir tes séminaires de Sylvain Gigan, p ex celui qu’il a fait à Polytechnique à Palaiseau, Dept De physique :
        https://enseignement.medias.polytechnique.fr/resources/r1261beca6d70nxvtlt6r6mblv0ibz/media_720_61kDY4jOfD.mp4?usage=download
        J’ai mieux compris l’usage des matrices aléatoires comme « outils agnostique de changement de dimensionnalité » à l’aide de sa présentation (« changement de dimensionnalité » on ne parle de pas de 3 à 2 mais de 10 000 000 à 5000 ou de 30 à 3000).

  6. Avatar de mouette
    mouette

    Le problème P vs NP est un problème majeur non résolu en informatique. Il s’agit de savoir si tout problème dont la solution peut être vérifiée rapidement peut également être résolu rapidement.

    Franchement, ça me parait complètement contingent, intuitivement parlant si la question n’est pas réduite à une famille de problèmes (logiques) extrêmement déterminée/spécifique.
    Je ne vois même pas pourquoi, même, il devrait y avoir un rapport entre les deux.
    J’aurais tendance, à la Wittgenstein, à y voir un pseudo-problème reposant sur des énoncés dépourvus de signification.

    Mais bon, l’intuition peut certes être mauvaise conseillère.

    1. Avatar de Paul Jorion

      Exactement, mais je voudrais cette fois-ci faire mes objections d’une manière qui convainque aussi les mathématiciens, et pas seulement les spécialistes des fondements des mathématiques non-mathématiciens de formation et les philosophes des sciences.

    2. Avatar de Ruiz
      Ruiz

      @mouette Si « la solution peut être vérifiée rapidement » c’est que l’on a une solution et alors cela prouve qu’elle a pu être résolue en temps fini dans un univers fini c’est à dire rapidement où alors que l’on a pas de solution mais que l’on prétends pouvoir la vérifier « rapidement » c’est à dire que celà ne concerne alors que des problèmes qui n’ont pas de solution (en pratique) ?

Répondre à Paul Jorion Annuler la réponse

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

Contact

Contactez Paul Jorion

Commentaires récents

  1. @ Ruiz, Un savoir c’est l’ensemble des connaissances/informations acquises par une personne ou une collectivité via l’étude, l’observation, l’apprentissage et/ou…

Articles récents

Catégories

Archives

Tags

Allemagne Aristote bancor BCE Bourse Brexit capitalisme centrale nucléaire de Fukushima ChatGPT Chine Confinement Coronavirus Covid-19 dette dette publique Donald Trump Emmanuel Macron Espagne Etats-Unis Europe extinction du genre humain FMI France Grèce intelligence artificielle interdiction des paris sur les fluctuations de prix Italie Japon John Maynard Keynes Karl Marx pandémie Portugal psychanalyse robotisation Royaume-Uni Russie réchauffement climatique Réfugiés spéculation Thomas Piketty Ukraine ultralibéralisme Vladimir Poutine zone euro « Le dernier qui s'en va éteint la lumière »

Meta