22 réflexions sur « Vidéo – P vs. NP : problèmes solubles et insolubles »

  1. Pour ceux qui voudraient avoir une idée de cet ouvrage, PDF téléchargeable
    (c’est gratuit et pas exactement légal) https://fr1lib.org/book/2225886/e1f1c6

    C’est assez pour que je sache que mon intellect n’est pas à la hauteur.

    Digression : je suis un client régulier de ce site Z-Library https://z-lib.org/ qui a toutes les apparences d’un site collaboratif dans l’esprit de Wikipedia (on peut ouvrir un compte ou non, on peut lire-télécharger, on peut ajouter un texte, le commenter, on peut aussi faire un don), tout en sachant que c’est la mort des auteurs et des éditeurs, et donc des livres, si tout le monde s’en sert. Pour calmer ma conscience, quand j’ai lu le livre et que je l’ai trouvé profitable, je l’achète (sur Amazon en général car je suis paresseux).

    D’un autre côté, la partie « articles » me donne accès à des textes qui me seraient inaccessibles, avec ou sans argent.

    Autre considération : ceux qui n’ont pas de pouvoir d’achat (par exemple les étudiants chinois que je connais) ne sont pas privés.

    Quelle est la pensée correcte sur ce sujet ?

    4
    1. Le marché du livre d’occasion évolue en permanence.
      Je cherche mes livres à dénicher, d’abord sur « Label Emmaus », ensuite « Recyclivre », deux boites qui font de la réinsertion et de faibles marges. Ensuite le site Rakuten, souvent moins cher que les autres portails commerciaux.
      Je visite aussi la boutique Oxfam de ma région, et j’y trouve parfois des pépites que je ne cherchais pas…
      Tout cela n’aide pas les auteurs ? J’achète aussi des livres neufs, mais je suis limité.

    2. J’obtiens alors :

       »  »  » Attention : risque probable de sécurité
      Firefox a détecté une menace de sécurité potentielle et n’a pas poursuivi vers z-lib.org. Si vous accédez à ce site, des attaquants pourraient dérober des informations comme vos mots de passe, courriels, ou données de carte bancaire.
      Que pouvez-vous faire ?
      Le problème vient probablement du site web, vous ne pouvez donc pas y remédier. Vous pouvez le signaler aux personnes qui administrent le site.
       »  »  »

      « Dangerous » or not ..?

      1. @Pierre Guillemot (mais pas seulement…)

        Complément : La situation Firefox décrite ci-dessus est liée au site de base proposé Z-LIBRARY….

  2. Gödel: «La position platoniste est la seule qui soit tenable. Par là, j’entends la position selon laquelle les mathématiques décrivent une réalité non sensible qui existe indépendamment aussi bien des actes que des dispositions de l’esprit humain et qui est seulement perçue de façon très incomplète par l’esprit humain.» (Collected Works, 1951, t III, p 323.)

    La mathématique ne se réduit pas au nombre. Pour moi Gödel n’était pas un platonicien, pas même un pythagoricien car tous ses travaux en logique formelle ignoraient complètement la géométrie (ce qui n’était pas le cas des pythagoriciens -loin s’en faut- qui prenaient grand soin de relier arithmétique et géométrie) (1).

    Thom: « C’est parce que la mathématique débouche sur l’espace qu’elle échappe au décollage sémantique créé par l’automatisme des opérations algébriques ».

    Thom a écrit en 1977 un article intitulé « Rôle et limite de la mathématisation en science » (article qui figure dans Apologie du logos-AL-, Hachette, 1990). Voici le début du chapeau et la conclusion:

    « Cet article reprend les avertissements que j’ai fréquemment lancés sur le caractère conceptuellement limité du domaine accessible aux modèles quantitatifs permettant la prédiction, et donc l’action. »;

    « Les perspectives ouvertes par la théorie des singularités sont considérables. Très probablement on va vers une nouvelle manière d’envisager le rôle des mathématiques en science. En reprenant le problème de la modélisation mathématique des activités psychiques, on peut espérer édifier une théorie mathématique de l’analogie ».

    Je rappelle que pour Thom la mathématique est une technologie de l’imaginaire alors que langage, mythologie, institutions sociales, n’en sont que des techniques (2).

    1: Georg Kreisel: « La comparaison en question conduit aussi au problème fort intéressant de l’intelligibilité d’une théorie des preuves qui soient effectivement intelligibles, et non seulement valides, en particulier de preuves combinatoires intelligibles. Le problème géométrique correspondant serait de trouver une théorie des constructions faisables, ne faisant intervenir que des points proches aux points de départ et stables pour de petits changements de données (cela réclame évidemment la métrique propre à l’intuition géométrique. » (Éléments de Logique Mathématique, Dunod, p.209).

    2: « Classification des sciences et des techniques », AL p.537.

    1
  3. Gödel, logicien formel: «La position platoniste est la seule qui soit tenable. Par là, j’entends la position selon laquelle les mathématiques décrivent une réalité non sensible qui existe indépendamment aussi bien des actes que des dispositions de l’esprit humain et qui est seulement perçue de façon très incomplète par l’esprit humain.» (Collected Works, 1951, t III, p 323.)

    Thom, géomètre, dit à peu près la même chose: « Car le monde des idées dépasse infiniment nos possibilités opératoires, et c’est dans l’intuition que réside l’ultima ratio de notre foi en la validité d’un théorème -un théorème étant avant tout, selon une étymologie aujourd’hui bien oubliée, l’objet d’une vision-« . (Apologie du logos, p.561)

    La mathématique ne se réduit pas à l’étude des nombres, car elle étudie les nombres, les figures et leurs rapports. Pour moi Gödel n’était pas un platonicien, pas même un pythagoricien car tous ses travaux en logique formelle ignoraient complètement la géométrie (ce qui n’était pas le cas des pythagoriciens -loin s’en faut- qui prenaient grand soin de relier arithmétique et géométrie) (1).

    Thom: « C’est parce que la mathématique débouche sur l’espace qu’elle échappe au décollage sémantique créé par l’automatisme des opérations algébriques ».

    Thom a écrit en 1977 un article intitulé « Rôle et limite de la mathématisation en science » (article qui figure dans Apologie du logos). Voici le début du chapeau et la conclusion:

    « Cet article reprend les avertissements que j’ai fréquemment lancés sur le caractère conceptuellement limité du domaine accessible aux modèles quantitatifs permettant la prédiction, et donc l’action. »;

    « Les perspectives ouvertes par la théorie des singularités sont considérables. Très probablement on va vers une nouvelle manière d’envisager le rôle des mathématiques en science. En reprenant le problème de la modélisation mathématique des activités psychiques, on peut espérer édifier une théorie mathématique de l’analogie ».

    Pour Thom la mathématique est une technologie de l’imaginaire alors que langage, mythologie, institutions sociales, n’en sont que des techniques (2).

    1: Georg Kreisel: « La comparaison en question conduit aussi au problème fort intéressant de l’intelligibilité d’une théorie des preuves qui soient effectivement intelligibles, et non seulement valides, en particulier de preuves combinatoires intelligibles. Le problème géométrique correspondant serait de trouver une théorie des constructions faisables, ne faisant intervenir que des points proches des points de départ et stables pour de petits changements de données (cela réclame évidemment la métrique propre à l’intuition géométrique. » (Éléments de Logique Mathématique, Dunod, p.209).

    2: « Classification des sciences et des techniques », AL p.537.

  4. [Scusi pour le presque doublon ci-dessus.]

    Je reviens encore une fois sur la correspondance de Curry et Howard, qui relie logique formelle et calculabilité (1):

    « Le logicien français Jean-Louis Krivine a fait le rapport entre différents théorèmes mathématiques et les programmes informatiques qu’ils représentent :

    l’absurde (appelé « bottom » : ⊥ correspond à une instruction d’échappement, d’exception, ou à un programme qui ne finit pas (un terme non typable dans le lambda-calcul simplement typé) ;
    le théorème d’incomplétude de Gödel qui dit qu’il y a des propositions qui sont indécidables correspond à un programme de réparation de fichiers;
    le théorème de complétude de Gödel correspond lui à un désassembleur interactif de programmes ».

    Plus généralement qu’une correspondance preuve/programme, je vois cette correspondance de Curry-Howard dans l’optique des oppositions puissance/acte et structure/fonction, la théorie et la structure étant du côté de la puissance alors que la pratique et la fonction sont du côté de l’acte. Dans les sociétés c’est la fonction qui crée l’organe (2) (pour remonter une horloge dont les rouages sont éparpillés, c’est un guide précieux de savoir qu’elle est faite pour indiquer l’heure…).

    En résumé la correspondance de Curry-Howard est pour moi plus qu’une correspondance preuve/programme, c’est une correspondance théorie/pratique (où théorie est pris au sens de la logique formelle : donnée d’un langage, d’axiomes et de règles de déduction, et où pratique est pris au sens de machine abstraite et de programmes exécutés par cette machine).

    1: https://fr.wikipedia.org/wiki/Correspondance_de_Curry-Howard#Logique_et_informatique

    2: Court métrage René(e)s de JL Godard sur Thom, à 39’45.

  5. PJ : « Le monde physique n’est pas entièrement réductible à sa modélisation mathématique ».

    Le premier ouvrage majeur de Thom s’intitule « Stabilité structurelle et morphogenèse », sous-titré « Essai d’une théorie générale des modèles ». Il a pour ambition de modéliser le monde physique (au sens moderne comme au sens ancien) et le monde psychique:

    « C’est sans doute sur le plan philosophique que nos modèles présentent l’apport immédiat le plus intéressant. ils offrent le premier modèle rigoureusement moniste de l’être vivant, ils dissolvent l’antinomie de l’âme et du corps en une entité géométrique unique. » (Conclusion de SSM)

    J’aime bien le PJ idéologue au sens étymologique (celui qui étudie les idées des autres -PJ anthropologue-, voire les siennes propres -PJ psychanalyste). Je n’aime pas le PJ à l’idéologie (au sens que la modernité donne à ce mot) étriquée: « Le monde physique n’est pas entièrement réductible à sa modélisation mathématique ». Qu’en sait-il?

    Thom : « Finalement, le problème de la démarcation entre scientifique et non scientifique n’est plus guère aujourd’hui qu’une relique du passé ; on ne le trouve plus guère cité que chez quelques épistémologues attardés – et quelques scientifiques particulièrement naïfs ou obtus » (1988, La science et l’intelligible).

    1. Merci pour cette nouvelle expression du culte populaire de Saint René-Thom. Vous me ferez 3 Ave et 3 Pater pour idolâtrie.

      Pouvez-vous revenir sur Terre et participer à un débat scientifique sans poussées occasionnelles de mysticisme ?

      2
      1. Thom :

        1. « (…) il y a une certaine opposition entre géométrie et algèbre. Le matériau fondamental de la géométrie, de la topologie, c’est le continu géométrique ; étendue pure, instructurée, c’est une notion « mystique » par excellence. L’algèbre, au contraire, témoigne d’une attitude opératoire fondamentalement « diaïrétique ». Les topologues sont les enfants de la nuit ; les algébristes, eux, manient le couteau de la rigueur dans une parfaite clarté. » ;

        2. « Pour moi, la mathématique, c’est la conquête du continu par le discret. » (et pour Grothendieck c’est peut-être le contraire: cf. ses topos…)

        Je répète que je trouve que votre pensée est étriquée (un peu comme celle de Gödel, en un certain sens…). Thom encore :

        « Ici on ne cherchera pas à convaincre, mais à susciter des représentations, et à étendre l’intelligibilité du monde » (Esquisse d’une sémiophysique, p.16).

        Vous semblez oublier la méditation, le rêve. Je suppose qu’un psychanalyste comme vous, qui vous intéressez néanmoins à la science, avez parcouru « La clef des songes; dialogue avec le bon Dieu » de Grothendieck.

        PS: Pendant que j’y suis, je réitère, pour la troisième ou quatrième fois, une question posée en commentaire de l’article de Yu Li:

        « La question est: dans l’énoncé original de son théorème d’incomplétude que vous avez sûrement sous les yeux, Gödel parle-t-il -à propos de PA1 ou de ZF pour fixer les idées- de cohérence syntaxique (cohérence interne), de cohérence sémantique (cohérence externe c’est-à-dire existence d’un modèle -où?-) ou de cohérence sans préciser.
        Pour moi, s’il s’agit de cohérence syntaxique, alors il y a peut-être là un « essential gap » -celui dont parle Zermelo-: c’est, je crois, le point de vue que défend PJ, lorsqu’il martèle qu’il doit y avoir deux niveaux de langage, l’un « méta » par rapport à l’autre. »

      2. Je ne comprends pas votre attitude vis-à-vis de Thom, sachant que, comme lui, vous défendez la dynamique d’affect (1) dans le début de « Comment la vérité… » (dans le but de défendre votre PSI?). Vous y écrivez en particulier p.53:

        « J’avais pu constater personnellement, au sein du panthéon des mêmes populations Xwéda (du Bénin actuel), le regroupement des phénomènes naturels en vastes catégories reproduisant les sept « catastrophes élémentaires » de la théorie géométrique des catastrophes due à René Thom »;

        (PJ: « Pouvez-vous revenir sur Terre et participer à un débat scientifique sans poussées occasionnelles de mysticisme ? ». Vous le faites vous-même p.53, ce rapport entre le Ciel et la Terre!)

        et p.58 où vous réitérez l’importance « essentielle » de l’affect en intelligence artificielle.

        Si certains des lecteurs de ce blog ont la curiosité de parcourir ces échanges, peut-être s’apercevront-ils que j’essaie d’apporter un autre point de vue -argumenté en plusieurs commentaires-, alors que l’unique et courte réponse de PJ me rappelle des arguments de cour de récréation d’école primaire :

        1: Cf. Esquisse d’une sémiophysique pp. 28 et 29 et pp. 72 et 73 (entre autres).

        1
      3. PJ empiriste (à la suite d’Aristote (1) et dans la tradition anglo-saxonne?) ?

        Je reprends d’abord partie du commentaire de Gaspard des montagnes (« évitons de mettre des verrous sur des portes que l’on a pas encore vu, pu ou su ouvrir. »). Je trouve que -si c’est le cas- PJ s’impose là un point de vue bien étriqué. Reproche qu’on peut difficilement faire à mon gourou Thom, qui écrit dès le début de « Esquisse d’une Sémiophysique » (sous-titré « Physique aristotélicienne et théorie des catastrophes »):

        « À ceux qui penseraient que la doctrine d’Aristote est fondamentalement périmée, je fais observer qu’on trouve chez lui une philosophie à la fois matérialiste (l’existence exigeant un substrat matériel), mais néanmoins régie par la forme et les causes finales. » (p.13) ;

        « Ici, on ne cherchera pas à convaincre, mais à susciter des représentations et à étendre l’intelligibilité du monde. » (p.16).

        Ce n’est pourtant pas comme ça que PJ présente Aristote (Aristote empiriste) dans « Comment la vérité…) :

        « L’ouvrage constitue un vigoureux plaidoyer en faveur d’un « retour à Aristote » (p.11) (où il se situe dans la tradition de Hegel, Duhem, Meyerson et Kojève) ;

        « Mais [dans nos civilisations occidentales] nous recourrons aussi bien et de manière tout aussi habituelle à la description fonctionnelle, qui rend compte du monde en terme de causes finales au sens d’Aristote (…); par exemple, « le papillon a une trompe pour pouvoir boire le nectar ».  » (p.180) ; (Aristote lamarckien avant l’heure? (2))

        « L’empirisme logique -héritier du cercle de Vienne- a mené un combat visant à ne reconnaître que la cause efficiente comme cause proprement dite, considérant la cause finale (ou téléologique) comme étant d’essence « mystique ». « (p180) ;

        « Hegel considérait tout au contraire que seule l’explication téléologique est digne de ce nom. » (p.180).

        PJ se situant dans la tradition d’Aristote et de Hegel (« mystiques » à leurs heures?) pour discrètement s’en détacher ?

        1: https://materialisme-dialectique.com/lempirisme-chez-aristote/

        2: Thom : « Enfin, last but least, Aristote évoque la présence, par analogie, de l’idée abstraite d’architecture dans la construction et la programmation des organogénèses. On voit ici ce qu’il y a de contradictoire avec la philosophie fondamentalement matérialiste d’Aristote : les Idées platoniciennes n’existent pas, mais il faut bien quelque chose comme une Idée pour diriger tout cet ensemble. Voici le modèle que je proposerai pour combler cette lacune (…). » (ES p.167).

  6. Bonsoir, sauf contre sens de ma part, vos propos m’ont rappelé la pensée de Castoriadis sur l’aspect “ensidique” du “réel” (ensembliste-identitaire), donc mathématisable, sans lequel la “déraisonnable efficacité des mathématiques” serait incompréhensible, mais insistant aussi sur le versant qu’il nommait “magmatique” du “réel” qui échappe précisément à cette mathématisation, mettant en avant le concept de création de formes nouvelles, dont on ne peut rendre compte dans le cadre d’une logique qui est par construction déductive. La pensée de Castoriadis est foisonnante, sur la politique, les sciences, “la” mathématique, etc… on se perd avec délices dans ses labyrinthes avec quelques carrefours pour s’y orienter (ou s’y égarer derechef).
    Mais peut-être me suis-je moi même égaré en entendant l’écho de la pensée de Castoriadis dans vos propos… Bonne soirée

    1. Le rapport entre les maths et la réalité est non seulement un vieux problème philosophique mais surtout le problème essentiel des rapports aporétiques entre le discret et le continu.

      Dans le commentaire qui suit PJ écrit : »C’est la vue d’Aristote et en ce qui me concerne, c’est de là que je la tiens ». C’est sa vision d’un Aristote logicien (de l’organon). Il y a aussi celle d’un Aristote topologue (de la physique) et dans « Aristotle’s two systems » D.W. Graham expose de manière systématique cette opposition entre ces deux aristotélismes, selon lui incompatibles.

      On aura deviné quel est l’Aristote que Thom admire : « Les Livres II et III de la Physique d’Aristote constituent à mes yeux l’un des sommets de l’esprit humain. », et il faut de se plonger (parcourir ne suffit pas, et de loin) dans Esquisse d’une sémiophysique et dans « Structure en fonction en biologie aristotélicienne » (1) pour se convaincre que cet Aristote-là n’a rien à voir avec l’Aristote cher à PJ, PJ qui a jadis sur ce blog répondu à l’un de mes commentaires:

      « Thom s’affirme constamment « aristotélicien » mais j’ai souvent beaucoup de mal à reconnaître dans l’Aristote dont il parle, celui qui m’est à moi familier. Dit de manière un peu plus directe : je n’ai pas le sentiment qu’il ait consacré beaucoup de temps à la lecture d’Aristote. ».

      Citation pour moi typique du PJ que je n’aime pas, à savoir du PJ idéologue (au sens que la modernité attribue à ce mot) à l’idéologie étriquée. PJ cite deux ou trois fois Esquisse d’une sémiophysique dans son « Comment la vérité… ». Peut-être pourrait-il en reprendre la lecture pour acquérir une vue plus dominante de l’œuvre d’Aristote?

      Remarque à propos de votre « mettant en avant le concept de création de formes nouvelles: « Thom sur Castoriadis : « La création est, en effet, une idée troublante, qui n’est pas fondamentale en philosophie et qui fait souvent l’objet d’un rejet virulent. Elle peut sembler philosophiquement inacceptable, voire scandaleuse. Qu’on songe, ici, à la réaction de René Thom, telle que la rapporte Castoriadis. L’auteur de la théorie des catastrophes, au demeurant nullement un héraut du déterminisme en sciences, aurait qualifié la thèse de la puissance créatrice de l’imaginaire de « pensée pour paresseux».

      (Je ne sais pas d’où vient cette citation. Mais je ne suis pas d’accord avec le « au demeurant nullement un héraut du déterminisme en sciences » de son auteur: voir la vidéo « Processus au hasard, déterminisme et innovation », accessible sur la toile.)

      Thom défend l’idée d’une origine géométrique du langage…

      1: Cet article figure dans Apologie du logos (Hachette, 1990)

        1. PJ: « Je dispose donc désormais d’un directeur de conscience ». Je propose et vous disposez, bien entendu.

          Un vieil adage français dit que seuls les cons ne changent pas d’avis. Cet adage, un autrichien -Wittgenstein- l’a appliqué à la lettre. Pourquoi pas vous qui avez actuellement choisi de camper dans le camp nominaliste (en y incluant Aristote, ce que vous reproche Thibault Gress)?

          Considérer que le langage a une origine géométrique -point de vue thomien- redonne de l’intérêt à la querelle des universaux. Le chapitre 8 de « Esquisse d’une Sémiophysique », intitulé « Perspectives aristotéliciennes en théorie du langage », commence par un paragraphe A intitulé: « Les universaux linguistiques ».

          Il y a pour moi un ordre des choses; réalité d’abord, vérité ensuite, démontrabilité enfin. Gödel a, je crois, cherché à montrer la supériorité de la démontrabilité sur la vérité, et je trouve tout-à-fait intéressante votre idée de montrer qu’il y a « un loup » quelque part dans son théorème d’incomplétude, et que c’est la vérité qui précède ontologiquement la démontrabilité.

          Je pense, quant à moi, que c’est la réalité qui précède ontologiquement la vérité, car c’est pour moi la réalité qui donne sens à la vérité: les assertions « tous les hommes sont mortels » et « Socrate est un homme » sont vraies car, de mémoire d’homme, tous les hommes ont fini par mourir et, de mémoire de contemporains transmise par oral ou écrit, Socrate était un homme. Tarski ne dit pas autre chose lorsqu’il définit la vérité/satisfaisabilité dans un modèle : il est vrai que « la neige est blanche » parce que … « la neige est blanche ».

          Thom: « La logique formelle ne fait que décrire la propagation des prégnances dans l’univers des propositions. Et la notion de « vérité » n’est à cet égard qu’une prégnance particulière. » La suite dans le premier paragraphe (« Introduction: le problème de l’a priori ») du premier chapitre de « Esquisse d’une sémiophysique ».

  7. Bonjour monsieur Jorion,
    Juste un mot pour vous dire que vous avez une tête à faire peur sur la photo !
    Je crois même déceler un souci à l’œil droit..
    Il faut (vraiment) vous reposer un peu. Vous seriez un ado, je vous priverais d’écran !

    Autrement de mon point de vue il n’y a que 2 types de problème : ceux que l’on a déjà résolus et ceux que l’on devra résoudre dans le futur, évitons de mettre des verrous sur des portes que l’on a pas encore vu, pu ou su ouvrir. Et comme disait Mark Twain « Ils ne savaient pas que c’était impossible, alors ils l’ont fait. »

    1. Je crois même déceler un souci à l’œil droit.. Il faut (vraiment) vous reposer un peu. Vous seriez un ado, je vous priverais d’écran !

      Merci pour votre sollicitude qui me donne l’occasion de remercier le bon dieu que vous n’ayez pas été ma mère 😀 .

      de mon point de vue il n’y a que 2 types de problème : ceux que l’on a déjà résolus et ceux que l’on devra résoudre dans le futur

      Cela simplifie en effet considérablement la question. Le souci des informaticiens n’en reste pas moins légitime de se faire une idée a priori au vu d’un problème s’il tombera dans la catégorie des problèmes solubles sur un plan pratique (recherche de taille polynomiale) ou insolubles (recherche de taille exponentielle).

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.

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