59 réflexions sur « Vidéo – P vs. NP »

  1. J’avais déjà un peu de mal avec la relativité générale et l’ordinateur quantique , alors là je ne me hasarderai pas à un commentaire pertinent , même si j’ai compris les enjeux qu’il pouvait y avoir dans les domaines pratiques, philosophiques , voire politiques .
    Malgré tout : pourquoi y aurait il un lien entre logique et temps ?

    1. Un ordinateur quantique doit sans doute élargir le domaine des solutions P dans la mesure où n bits stockent n informations là où n qubits peuvent stocker 2 puissance n informations et les “gérer” à la vitesse de la lumière .

      Mais ça ne donne pas pour autant l’algorithme qui pose la question à résoudre , et les questions actuellement résolues par les ordinateurs quantiques sont d’un “intérêt” encore peu valorisé ( sauf si ça permet de décrypter les clés SAT des banques suisses comme évoqué dans la vidéo de David Louapre ! ) .On répond ” plus vite” ( et considérablement , par contre ) à une question qu’on savait déjà résoudre en y mettant le temps , mais ça ne démontre pas qu’on saura ainsi pour autant répondre à des questions plus ….” inconcevables”.

      Peut on trouver autre chose que ce que l’on cherche ( cf le pêcheur et le choix de ses filets ) , et si oui pourquoi et comment reconnait on qu’on a trouvé autre chose que ce que l’on cherchait ?

      Réflexion ” foireuse” soumise à un algorithme ” bienveillant” .

  2. N’ayant ni le talent, ni les compétences pour résoudre certains problèmes complexes, j’en suis venu à m’en remettre à ce que j’appelle l’« accumulation pertinente ». C’est-à-dire que, me fiant à la supériorité de mon inconscient sur mes capacités intellectuelles conscientes, j’accumule les contacts avec les informations me semblant pertinentes en espérant que, en s’ajoutant aux autres informations de tous ordres encombrant mon esprit, elles contribueront à orienter mon inconscient dans la résolution du problème, dans un eurêka volcanique.

    Mais à ce jour, ça n’a pas marché… 😉

    2
    1. Si l’on pose qu’une éruption volcanique est la résultante de forces préexistantes , “l’euréka volcanique” serait sans doute une autre traduction de P vs NP .

      Si “ça n’a pas encore marché” , on pourrait logiquement proposer que :
      – ou bien ,il n’y a pas encore suffisamment d’accumulation pertinente ( effet de seuil )
      – ou bien les informations accumulées ne sont pas assez pertinentes ,
      – ou bien ,il n’y a rien à attendre de l’accumulation pertinente ,
      – ou bien “l’inconscient” ,on ne sait pas trop ce que c’est ou comment ça marche , et l’accumulation se fait dans un abysse ,
      – ou bien la pertinence ça n’existe pas ,
      – ou bien “euréka” (intuition , l’esprit de finesse ) n’existe pas ,
      – ou bien “euréka” , comme l’amour , se manifeste sans qu’on sache où, quand , comment et pourquoi ,
      – ” à ce jour” : qu’est ce que le temps ?
      – ou bien …
      – ou bien combinaison de tout ou partie de tout ça .

  3. de conjecture en conjecture……
    étant un des rares commentateurs foncièrement pessimiste (je dirais “lucide” pour me rassurer ) sur ce “site de l’optimisme” , je dirais P ≠ NP.
    mais , il est bien évident que l’on touche au summum du Sens des choses , car si jamais P = NP , “TOUT” est possible , non ?
    les prothèses d’intelligence que nous appelons IA sont des créations humaines , donc imparfaites.
    si N=NP , il n’y aurait plus rien à démontrer.
    le fait qu’en ce moment même j’écrive ces mots confirme mon hypothèse (P ≠ NP) , sinon , il n’ y aurait plus RIEN à DIRE .

    2
    1. Ça , ce n’est pas une preuve , c’est une illustration des démonstrations foireuses évoquées par Paul Jorion , du style preuve par l’absurde ( ou par “l’horrible” en l’occurrence , mais Jean Rostand , qui n’était pas mathématicien l’avait déjà dit ) .

    2. @Juannessy
      “Ça , ce n’est pas une preuve ”
      vous êtes tombé dans le piège …
      je n’ai rien cherché à “prouver” +++ , donc il n’y a (lisez-bien ce que j’écris ) rien à démontrer (“foireusement” ou autrement , merci de l’adjectif) , dans la mesure où l’énoncé s’invalide de lui-même par son énonciation.
      dommage que vous n’ayez saisi l’aspect méta-physique de mon propos.

      1. @Juan
        le méta , c’est l’après , le fait d’aller au delà d’où nous en sommes actuellement …..

        rien avoir avec un dispositif idéologique prédéfini (une religion , un concept politique (je pense au communisme)) centré de façon totalitaire sur l’idée de définir (temporairement ) une frontière entre un bien et un mal (je pense au “parfait” des Cathares) , une morale en guise de politique , en somme.

        pour reprendre votre expression triviale de “foireux” , finalement je la fais mienne , et j’engage à faire une “foire” aux idées iconoclastes dont nous avons besoin pour inventer un méta-monde plus humain que celui dans lequel nous nous enfonçons.

        1. – votre première ligne est un axiome qui n’engage que vous ,
          – ” méta” exprime certes ” l’au delà ” ( dans l’espace ? dans le temps ?dans la complexité ? dans …? ) , mais aussi une idée de changement et d’une forme “d’association ” ( de qui ? de quoi ?)
          – mais si le “méta” ouvre d’un côté , il ferme de l’autre car il subordonne ” a priori ” , entre eux , les temps et les objets proposés à l’examen . Il pose qu’il y a un grand tout sans l’avoir “démontré ” par la logique . C’est un acte de foi , pas de logique .
          – j’utilise bien ” foireux” dans le sens de ” gratuitement asséné” . Pas dans ses sens plus triviaux ( qui n’auraient pas du chatouiller un pessimiste fondamental et revendiqué mais qui espère quand même dans un méta monde !) .
          – S’il y a un méta monde universellement souhaitable et souhaité , je vois mal comment il pourra être “déconnecté” du monde tout court .

          1. @Juan
            “votre première ligne est un axiome qui n’engage que vous”
            tous les axiomes fonctionnenent de la même manière : de άξιόω (axioô), « juger convenable, croire juste »)
            c’est donc une proposition non démontrée…soit….
            mais quand vous dites ” si le “méta” ouvre d’un côté , il ferme de l’autre car il subordonne ” a priori ” , entre eux , les temps et les objets proposés à l’examen . Il pose qu’il y a un grand tout sans l’avoir “démontré ” par la logique . C’est un acte de foi , pas de logique .” vous tombez dans le même panneau , tout en le déniant , ce que je me garde bien de faire.
            je vous répète que je ne cherche pas à démontrer quoi que ce soit .
            il ne s’agit que d’un jugement , expression de ma propre subjectivité.
            si vous tenez à garder de mot “foi” , je dirais que je crois en ce que j’énonce , en toute modestie d’ailleurs.
            je pense que s’il y a une révolution possible , elle se situe dans ce sens .
            “” foireux” dans le sens de ” gratuitement asséné””… c’est bien mal me connaitre , j’assène rarement et je pense que tout a un prix.
            ” je vois mal comment il pourra être “déconnecté” du monde tout court .” , merci de m’expliquer ce qu’est “un monde tout court” et surtout ce que vient faire là le terme “connecté”.
            je crains qu’il n’y ait un malentendu.
            pour ma part , il est bien clair que quand je parle de méta-monde , je ne parle pas d’un “au delà” mystico-mythique , mais d’une mutation (c’est à la mode) du monde actuel , suffisante pour qu’il (le monde) n’ait pas tout à fait les mêmes propriétés que maintenant sans pour autant représenter un ailleurs , un au delà .
            la métaphore des variants de virus est une bonne représentation…
            mon pessimisme vient de ce que je crains qu’homo-sapiens n’est pas les outils pour dépasser les défis actuels.
            bon , je vous l’accorde , c’est difficile de débattre de sujets aussi complexes dans ce cadre là….

            1. Un axiome engage tout le monde et il vaut donc mieux que chacun en soit “d’accord” ( ou connecté si ça éclaire connecté ) , sinon ça n’est qu’un postulat personnel .

              Je suis aussi évidemment d’avis qu’un “changement d’état” , c’est une ” mutation ” aussi bien dans P que dans NP .

              Mais c’est une mutation selon Racine ou selon Corneille ?

            2. @ Juan
              “Un axiome engage tout le monde ”
              bien sûr , mais avant d’engager tout le monde ,dans un premier temps , il n’engage que son auteur…à lui de convaincre de son universalité.
              c’est bien l’état dans lequel se trouve notre monde actuel , des axiomatiques qui ne produisent plus de démonstration possible quand à gérer l’état dans lequel se trouve notre humanité.
              donc , à nous de créer une nouvelle axiomatique qui pourrait nous amener à trouver un passage dans l’impasse dans laquelle nous sommes.
              toutes les idées “foireuses” sont les bienvenues …
              le tri de ce qui peut servir d’axiome se fera tout seul.

              par ailleurs , vous ne pouvez pas dire “votre première ligne est un axiome qui n’engage que vous” , car , dans la mesure où cela n’engage que moi , ce ne peut être considéré comme un axiome (ce dont je conviens) , soyons logique !

              grand dieu , que voulez-vous (dé)montrer ?

              1. Vous avez bien repris la différence entre axiome et postulat .

                Je ne veux rien démontrer , je fais , comme déjà évoqué , ainsi que Cro magnon , je tape sur le caillou et je (dé) monte , comme , gamin , je démontais les réveils pour voir comment c’était foutu et repérer ce qui résiste .

                Pour la pépinière à axiomes , je suis plus modeste que vous , même s’il est tentant de proposer des ” au delà” qui chantent à partir de nouveaux paradigmes , d’autant que le boulot a déjà été pris par Paul Jorion et Vincent Burnand Galpin .

                La ” foire à l’au delà ” a d’ailleurs pas mal d’étals , et je me souviens de l’un d’eux qui proposait déjà un au delà du marché ( gratuité) , un au delà de la démocratie ( démocratie plus directe encadrée par la ” responsabilité” ) , et un au delà du spectacle ( le savoir) .

                Mon ” au delà ” personnel se manifeste chaque matin quand ma carcasse me le susurre à l’oreille .

              2. @Juan
                dommage que vous ne vouliez que dé-monter , plutôt que de dé-mon(s)trer….
                pour ma part , ayant également depuis ma tendre enfance démonté quelques réveils, poste de radio , puis vélomoteurs, automobiles, ordinateurs ……. , il me paraissait aller de soi de passer aux démonstrations , sans grand succès , pour le moment (et le moment laisse peu d’espoir)

                “Pour la pépinière à axiomes , je suis plus modeste que vous…”
                je ne sais pas si c’est de l’absence de modération de ma modestie , mais plutôt une quête de sens rédhibitoire …

                enfin , quand vous dites ” d’autant que le boulot a déjà été pris par Paul Jorion et Vincent Burnand Galpin”, pourquoi enfermer certaines personnes dans certains registres de compétences ?
                Je crois bien que vous pointez , sans vous en rendre compte , l’essentiel de ce qui me parait être le problème fondamental de notre temps : l’hyper-hubricisation de la pensée (désolé pour le néologisme).
                une véritable modestie s’impose à nous tous , si nous voulons pouvoir imaginer le futur.
                mais , je n’espère pas , comme vous me le prêtiez ci-dessus , je ne peux tout simplement pas “m’empêcher de” ….

                1. Je ne comprends pas ce qu’est ” l’hyper hubricisation de la pensée” .

                  Si vous n’espérez pas , laissez aller , tout est prévu .

                  1. @Juan

                    “Si vous n’espérez pas , laissez aller , tout est prévu”…… un postulat ou un axiome ?
                    hyper-hubricisation = le comble de l’hubris (la démesure)….

                    1. 1- quand on n’espère rien ( de favorable j’imagine ) , c’est “a priori” qu’on ne se donne pas de chances d’avoir prise sur le réel ( le contraire de ” je suis maître de moi comme de l’univers “) , et qu’on s’en remet donc au “destin” et à la marche des ” lois de l’univers ” ( je me livre en aveugle au destin qui m’entraine” ). Bernard , lui , est le contraire du désespéré , et il ambitionne de joindre le geste à la parole .

                      2 – je savais à peu près ce que désigne l’hubris , je mesure moins bien ce que peut être un hyper-hubris , mais surtout je ne vois pas en quoi reconnaitre le travail de Paul Jorion et VBG ou celui de quelques autres , ce serait célébrer un hymne à l’hubris . J’aurais plutôt tendance à regretter que leurs travaux ne soient pas valorisés et déclinés , plutôt que d’avoir envie d’en rajouter ( des paradigmes nouveaux , inouïs et salvateurs ) .

                    2. @Juan , Bonjour,
                      ” quand on n’espère rien ( de favorable j’imagine )”
                      vous déformez totalement ce que j’essaye de dire……
                      qui pour ce qui concerne la citation ci-dessus , vous invite à faire coexister les termes “espérer” et “rien”….. pour ma part , je n’ai pas besoin de croire espérer , pour continuer à essayer de comprendre le monde dans lequel je vis , et ,comme je le dis plus haut , je ne peux m’empêcher de ….
                      Un de nos illustres avait dit ainsi la chose :
                      “En 1847, Victor Hugo nous rapporte que le savant François Arago aimait à raconter l’anecdote suivante : lorsque Laplace publia les derniers tomes de son Traité de Mécanique céleste, l’empereur Napoléon le convoqua et l’apostropha, furieux : « Comment, vous donnez les lois de toute la création et, dans tout votre livre, vous ne parlez pas une seule fois de l’existence de Dieu ! – Sire, répondit Laplace, je n’avais pas besoin de cette hypothèse”.

                      mais bon , je conçois que je puisse mal m’exprimer.

                      “mais surtout je ne vois pas en quoi reconnaitre le travail……”
                      nulle intention pour moi de ne pas reconnaitre le travail de chacun.
                      mon souci étant , sans en rajouter et plutôt en essayant d’être plus concis (donc l’inverse de la démesure dont je parle en évoquant l’hubris) , de participer à trouver le chemin qui pourrait nous mener vers une “Common decency” que nous semblons avoir perdu.
                      nous semblons avoir laissé envahir le champs de la connaissance par l’analytique au dépends du synthétique , ce qui nous a enfermé dans une aporie.
                      comment vous faire “sentir” que nous ne nous comprenons pas (ce qui peut être une étape à dépasser , bien sùr ) , et , tout cas , que je ne fais que noter votre incompréhension eut égard à ce que j’essai d’expliciter.
                      où se trouve le passage ?
                      je ne sais comment faire.
                      quand au néologisme “hubricisation” (je ne parle pas du terme “hubris”) , c’est cette installation dans la démesure , démesure , non dans son aspect moral , dont je me contre-fiche , mais littéral : perte de sens de la mesure.
                      ce qui me semble rejoindre ce que je perçois depuis quelques dizaines d’années (début des années 1990) concernant l’installation d’une anomie.
                      j’étais d’ailleurs heureux d’entendre hier soir mon illustre confrère B.Cyrulnik évoquer ce problème d’anomie .

    3. @ A113,

      J’ai toujours espéré que P ≠ NP soit l’hypothèse vérifiée… Dans le cas contraire, celà voudrait dire que l’IA pourrait devenir aussi (si ce n’est plus) humaine que l’humain…

      1. Ça voudrait surtout dire que nous sommes limités intellectuellement, car il y aurait des problèmes pour lesquels on serait certains qu’une solution existe mais qu’aucun d’entre nous n’est assez malin pour la trouver. Grosse leçon d’humilité à la clé…

        1
  4. Pour ceux qui ne connaissent pas, voilà une présentation du problème P vs NP par David Louapre :

    Bon, c’est bien la seule contribution que je pourrai faire 🙂

    2
  5. “Revenir à la bifurcation ” demanderait de cerner à quel moment et pourquoi les enjeux de disciplines ont-ils commandé l’entubage des générations suivantes de matheux ( à 90¨des ingénieurs) par l’argument de la diagonale. Certes 99% les 10% de mathématiciens étaient déjà platoniciens, comme ils le sont toujours.

    Je me souviens, de mes lectures de jeunesse, qu’Alain Badiou ( Le concept de modèle, 1969 ) nous avait proposé une lecture décapante du théorème de Gödel, laquelle allait dans le même sens, de l’inversion de la primauté du « modèle » sur la réalité, telle qu’elle est proposée par” Comment la la Vérité et Réalité et inventées” (ce dernier ouvrage étant bien plus profond que ne le fut celui de Badiou)

    Pourquoi vouloir dialoguer avec le 0,001 % des mathématiciens qui s’occupent de ces chinoiseries pour les convaincre de leurs erreurs épistémologiques, et pourquoi ne pas reprendre le chemin ouvert par Seymour Papert, et reconstruire les mathématiques de façon opérationnelle, dès le jardin d’enfants ?

    Pourquoi ne pas dialoguer avec l”Education populaire?

    2
    1. Sans doute parce que j’ai déjà un peu de mal avec les mathématiques , l’écriture et votre premier paragraphe .

  6. Hofstadter Douglas, Gödel, Escher, Bach : Les brins d’une guirlande éternelle, Paris, Dunod, 2008, 928 p.
    Lisible, sur Gödel et aussi (surtout) sur l’intelligence artificielle… mais pas que…

  7. Légèrement hors sujet mais le retour à une bifurcation me semble un facteur essentiel pour une bonne pratique démocratique. Voir ainsi ” effet cliquet “.

    1. Que signifie une bifurcation dans P ?
      Que signifie une bifurcation dans NP ?

      Bifurcation suppose déjà qu’il y a une direction et un sens , et une possibilité de choix aléatoire ou déterminé .

      Mais il est patent que la sincérité de la pratique démocratique a totalement à voir avec la conjecture proposée .

  8. Une petite citation médiévale, pour éclaire le débat:

    “Creatio numerorum, rerum est creatio.”

    Thierry de Chartres, Hexaméron (XIIe siècle).

    Enjoy!

  9. Addendum:

    Cher monsieur Jorion, par simple curiosité, vous a-t-on déjà objecté le nom de René Guénon, lors de vos discussions entre mathématiciens?

      1. Merci!
        Pour Fulcanelli, je verrais plutôt Timiota, non?
        Plus sérieusement, je m’interroge sur la redéfinition du champ d’investigation (mathématique) comme espace de libération d’un impetus sacrilège qui vient de loin, très loin, dans l’histoire et dans l’histoire du psychisme.
        En tout cas, je continue à vous lire avec grand intérêt.

  10. Bien sûr chercher le contraire d’une licorne verte (un hippopotame rouge ? ) est absurde mais cela implique-t-il qu’il est absurde de faire des démonstrations par … l’absurde ? Je ne le crois pas.
    Tout d’abord il faut considérer le concept de contraires sans ce genre de caricature qui clôt le débat.

    Dans la nature il y a effectivement des contraires ou plutôt des oppositions binaires et exclusives l’une de l’autre dans tous les domaines tels les dipôles magnétiques ou certains types de canaux synaptiques ouverts ou fermés ou même in fine, « mort ou vivant ». Toute notre technologie informatique est d’ailleurs basée sur le traitement des 1 et 0 et leur stockage qui est également binaire quel qu’en soit le support. En mathématique, il est possible qu’une des premières découvertes (ou inventions) soit celle du pair ou de l’impair pour les nombres entiers ─ parité : une situation où deux chasseurs peuvent se partager des proies sans se taper dessus.

    Cette opposition par contraires de ce type (c’est-à-dire strictement définis) est tout à fait valide pour établir une preuve par l’absurde et Aristote lui-même l’aurait admise pour démontrer l’irrationnalité de racine de deux. Je ne rentrerai pas dans ce débat qui est exposé dans cet article [Une nouvelle démonstration de l’irrationalité de racine carrée de 2 d’après les Analytiques d’Aristote (openedition.org) = https://journals.openedition.org/philosant/2120#:~:text=Or%2C%20chez%20les%20auteurs%20anciens,comme%20un%20r%C3%A9sultat%20en%20soi.&text=Si%20la%20preuve%20vis%C3%A9e%20par,2%20serait%20un%20cas%20particulier. ] mais je recopie cet extrait où se trouve une citation éclairante du Stagirite :

    « L’irrationalité en mathématique intéresse non seulement les historiens des sciences, mais
    également les philosophes. Ainsi Aristote y fait-il plusieurs allusions dans les Premiers analytiques, sans en expliciter la démonstration. Par contre, il la commente de la manière suivante :
    “On prouve, par exemple, l’incommensurabilité de la diagonale, par cette raison que les nombres impairs deviendraient égaux aux nombres pairs, si on posait la diagonale commensurable ; on tire alors la conclusion que les nombres impairs deviennent égaux aux nombres pairs, et on prouve hypothétiquement l’incommensurabilité de la diagonale par ce qu’une conclusion fausse (ψεῦδος) découle de la proposition contradictoire. Car tel est, avons-nous dit, le raisonnement par l’absurde (διὰ τὸ ἀδυνάτου) : il consiste à prouver l’impossibilité (ἀδύνατον) d’une chose au moyen de l’hypothèse concédée au début.” (An. pr. I, 23, 41a26-32, trad. Tricot.) Assertion qu’il reprend en la résumant un peu plus loin (I, 44, 50a37-38).
    La démonstration dont il est question ici, est donc un raisonnement ‘’par l’impossible’’ (ou ‘’ par l’absurde’’ .»

    Les méthodes de démonstrations mathématiques sont très diverses, souvent innovantes (cf. Cantor), mais toutes sont valables car justement selon l’étymologie [μαθήματα ], les mathématiques sont « les choses qui peuvent s’apprendre », cela par la raison mais jamais et en aucune façon par l’expérimentation au sens des sciences physiques (qui peuvent certes inspirer des découvertes mathématiques). Réduire les maths aux maths appliquées est réducteur et conduit rapidement à des impasses. Les objets mathématiques sont des créations abstraites, au début abstraites à partir de la nature (cf. idées du cercle ou du carré qui n’existent pas dans la nature) et ensuite construites par étapes successives (cf. les nombres ‘imaginaires’ ou bien N & NP). Quant à leur étrange efficacité pour comprendre, décrire ou modéliser des phénomènes naturels, c’est un autre débat …

    1. Copeland, The Essential Turing, Oxford UP, 2004 : 578

      Having introduced the normal form principle for puzzles, Turing turns to his central project of establishing that ‘there cannot be any systematic procedure for determining whether a puzzle be solvable or not’ (p. 590). In particular, there cannot be a systematic procedure for determining whether substitution puzzles are or are not solvable. Turing argues by reductio ad absurdum. He shows that the supposition that there is a systematic procedure for determining whether substitution puzzles are or are not solvable leads to an outright contradiction, and on that basis concludes that there can be no such procedure. The argument turns on the impossibility of applying a certain procedure to itself.

      Any systematic procedure is in effect a puzzle, since in following the procedure one applies rules to some ‘starting position’ until one or another result is achieved. So if there were a systematic procedure for determining whether each puzzle is or is not solvable, then by the normal form principle, there is a substitution puzzle — call it K — that is equivalent to this procedure. When applied to any substitution puzzle, K — if it exists — must ‘come out’ either with the result solvable or with the result not solvable. Since K is applicable to any substitution puzzle, K can be applied to itself in order to determine whether it itself is or is not solvable. Turing shows (p. 592) that this supposed ability of K to pronounce on its own solvability leads to outright contradiction, and so concludes that K cannot exist.

      Or ce n’est pas une contradiction, c’est un recours à un procédé illégitime : l’auto-référencement.

      Ladrière, Les limitations internes des formalismes, Nauwelaerts 1957 : 74

      Les paradoxes syntaxiques, tel celui de Russell “conduisent à des contradictions lorsqu’on n’établit aucune distinction entre les catégories d’expressions qu’il font intervenir. La théorie des types […] qui établit une hiérarchie des niveaux d’expressions, permet de les éliminer”.

      1. D’accord, on peut considérer comme “illégitimes” des procédés avec auto-référencements qui n’éliminent donc pas les hiérarchies des niveaux d’expressions.
        Mais pour autant peut-on ramener TOUS les raisonnements “reductio ad absurdum” à ce genre d’explorations d’un niveau plus général : solvabilité, complexité, théorie des ensembles (le menteur crétois, l’ensemble des ensembles … )?
        Dans l’exemple que j’évoquais (basique mais fondamental) il est clair qu’il est possible de le faire car en aucune façon un nombre entier ne peut être pair et impair en même temps. Il y a d’autres exemples et ils font intervenir la question des choix axiomatiques (cf. les géométries). Il n’ a là aucun auto-référencement.
        Il me semble qu’il faudrait dans les cas de raisonnements par l’absurde considérer en effet les risques induits en manipulant certains concepts (où les “contradictions” sont des illusions que l’on doit contourner par les “métalangages”) mais en conserver la puissance heuristique quand on manipule des propositions “simples” tel que la parité.

    2. Comment la vérité et la réalité furent inventées, Gallimard 2009 : 93-94

      Pour Aristote : “Les prémisses du syllogisme peuvent être exprimées de manière positive, affirmant que certaines choses sont de telle ou telle nature ou bien possèdent un attribut particulier. Ce type de syllogisme fournit le mode de raisonnement le plus parfait. D’un degré moindre quant à la force persuasive sont les syllogismes où les prémisses sont exprimées négativement : lorsqu’on déclare que certaines choses ne sont pas de telle ou telle nature ou sont privées de telle ou telle propriété. D’un statut encore moins élevé sont ceux utilisés de manière hypothétique dans ce qu’on appelle aujourd’hui la « preuve par l’absurde » mais que les auteurs anciens et les Scolastiques appelaient, selon les termes utilisés par Aristote, la preuve per impossibile (adunaton), c’est-à-dire « selon l’impossibilité ». La justification de cette appellation est que, par la faute de l’une des deux prémisses, la conclusion formule une impossibilité : à savoir qu’un état de fait et son contradictoire sont simultanément vrais. Pour éliminer l’anomalie, la prémisse coupable doit être inversée en sa propre contradictoire ; on obtient en fin de compte un syllogisme auquel on a abouti de manière « expérimentale ». La preuve par l’absurde, en dépit de ses succès dans l’histoire des mathématiques, est aux yeux d’Aristote un moyen argumentatif plutôt faible en raison de la formulation initialement hypothétique et de la difficulté qui existe ensuite à découvrir pour une proposition sa contradictoire unique, un ensemble de contraires se présentant généralement spontanément à la pensée. De manière révélatrice, lorsque l’auteur d’un ouvrage mathématique récent, Fundamentals of Mathematical Analysis, dresse la liste des modes habituels de preuve mathématique, il propose – sans le savoir – les trois formes de démonstration propres à l’analytique aristotélicienne : 

      « De nombreux théorèmes mathématiques prennent la forme (P Q). Pour montrer que P implique Q, on adopte généralement l’un des trois schémas suivants :

      La première méthode, qui constitue une méthode de preuve directe, suppose que P est vrai et tente, par un certain développement, de déduire que Q est vrai. Comme (P Q) est vrai lorsque P est faux, il n’est pas nécessaire d’envisager le cas où P est faux.

      La deuxième méthode est indirecte. On écrit d’abord le contre-positif ((non Q) (non P)), et l’on s’efforce de prouver directement l’affirmation équivalente. Autrement dit, supposons que Q soit faux, (c’est-à-dire (non Q) est vrai) et déduisons-en que P est faux (c’est-à-dire (non P) est vrai). 

      La troisième méthode couramment utilisée est la preuve par contradiction (encore appelée preuve par l’absurde). Dans ce type d’argumentation, supposons que P soit vrai et que Q soit faux (c’est-à-dire (non Q) est vrai) et déduisons-en une affirmation manifestement fausse. Ceci montre que l’hypothèse originale (P et (non Q)) doit être fausse. Autrement dit, l’affirmation (non (P et (non Q))) est vraie. Laquelle est l’équivalent logique de (P Q) » (Haggarty 1993 : 22-23).

      On aura reconnu dans la présentation de Haggarty et dans l’ordre, 1° le syllogisme ayant deux prémisses positives, 2° le syllogisme ayant deux prémisses négatives, 3° le syllogisme utilisé dans une preuve per impossibile ou « par l’absurde ».”

      1. Toute la question est bien là :
        « la difficulté qui existe ensuite à découvrir pour une proposition sa contradictoire unique»
        Une fois cela résolu (et je reviens à nouveau sur mon exemple initial de la parité des nombres) je ne vois pas en quoi on peut argüer qu’il y aurait des modes argumentatifs plus faibles que d’autres. Les qualifier de faibles est une facilité de métalangage, l’affaire concerne plutôt selon moi la robustesse de toute la construction de la mathématique jusqu’à nos jours. Si des raisonnements ‘per impossibile’ sont solides (grâce aux réserves indispensables décrites dans ton texte), pourquoi les exclure au nom d’un dogmatisme de la pureté ou de la force/faiblesses?
        Soit ils tiennent la route pour le dire familièrement, soit soit ils ont un défaut rédhibitoire car en fait on n’a pas réussi à établir la contradictoire unique. Et il est vrai qu’il faut énormément se méfier du “spontané” , à la fois source créative (l’intuition des matheux) et source d’erreurs.

          1. Je crois que quand les matheux ont une intuition on appelle ça de la physique 😉

            Intuitivement on se demande pourquoi l’univers déploie autant d’ingéniosité pour que les problèmes NP de mécanique ne soient pas vraiment P… pauvre Newton 🙂

        1. Merci Jacques, vous allez me permettre de recopier entièrement ici mon Comment la vérité et la réalité ont été inventées, 2009 : pages 309-311

          Le second théorème de Gödel recourt à certains modes de preuve parmi les plus faibles : comme ici, la preuve « par l’absurde » et comme on l’a vu plus haut, la récursion ou « induction complète », sans que Gödel ni ses commentateurs ultérieurs ne fassent la moindre observation à ce sujet. Or, les adversaires « constructivistes » de Gödel avaient adopté quant à la preuve par l’absurde une position très claire : ils l’avaient exclue des modes de preuve valides. Barrow explique cela : « N’accepter comme arguments logiques que ceux acceptés par les constructivistes, signifie éliminer certains procédés familiers tel que l’argument par contradiction (la reductio ad absurdum) […] Si l’on adopte la philosophie constructiviste, le contenu des mathématiques s’en trouve considérablement réduit » (Barrow 1991 [1990] : 186). Or, et comme le souligne encore Barrow, l’exclusion de la preuve par l’absurde a d’autres conséquences sérieuses : en particulier en physique où elle interdit le recours au « Big Bang » comme principe explicatif : « Les conséquences d’un tel recalibrage sont également significatives pour le scientifique. Nous serions obligés en effet d’abandonner certaines déductions fameuses telles que les “théorèmes de singularité” de la relativité générale qui spécifient les conditions qui, lorsque la structure d’un Univers et de son contenu matériel les satisfont, suffisent à indiquer l’existence d’un moment passé où les lois de la physique ont dû être suspendues – la singularité que nous appelons “Big Bang”. Car ces théorèmes ne constituent pas ce moment explicitement, en fait, ils recourent au procédé de la reductio ad absurdum pour montrer que sa non-existence conduirait à une contradiction logique » (ibid. :187). 

          Le théorème fait également intervenir de manière très cavalière la notion de « contraire » ou plutôt de « contradictoire » d’une proposition. Je peux dire, « Le chat est un mammifère » et le contraire, « Le chat n’est pas un mammifère » ; le contradictoire serait : « Certains chats ne sont pas des mammifères ». D’une chose et son contraire, l’une des deux seule est vraie. Je peux dire aussi « Tous les chats sont des fromages » et « Aucun chat n’est un fromage », ici aussi, une seule des deux propositions est vraie. Dans mes exemples, les deux propositions vraies sont, « Le chat est un mammifère » et « Aucun chat n’est un fromage ». Maintenant imaginons qu’il existe deux livres sur les chats, le premier néglige de mentionner que « le chat est un mammifère », le second oublie de dire qu’« aucun chat n’est un fromage ». Lequel achetez-vous ? La bonne réponse est : le second. Pourquoi ? Parce que la première proposition signale un attribut essentiel du chat, la seconde, un attribut qui, s’il est vrai est néanmoins sans portée, du fait que la liste est quasi infinie des choses que les chats ne sont pas. Hegel écrit à ce propos, « L’opposé signifie ici simplement le manque, ou plutôt, l’indéterminité ; et la proposition est si insignifiante que ce n’est pas la peine de la dire. Si l’on prend les déterminations doux, vert, carré – et l’on doit prendre tous les prédicats -, et si l’on dit maintenant de l’esprit qu’il est ou bien doux ou bien non doux, vert ou non vert, etc., c’est la une trivialité qui ne conduit à rien » (Hegel 1981 [1816] : 80). Guillaume d’Ockham s’était déjà intéressé à ces questions. Broadie écrit : « … Ockham nie qu’ “Une chimère est un non-homme” soit équivalant à “Une chimère n’est pas un homme”. À ses yeux, la première proposition est fausse alors que la seconde est vraie. En effet, comme Ockham le note, il faut conclure qu’une chimère n’est pas davantage un non-homme qu’un homme » (Broadie 1987 : 30). Or, la démonstration du second théorème de Gödel regorge de ce genre de trivialités. Au début de la Proposition VI on définit la proposition Q’(x, y(u)) comme étant Non [x B y (Gy)]…, « c’est-à-dire que x n’est pas une “preuve” de la formule obtenue en substituant pour la variable dans la classe-signe y(u) le nombre gödelien Gy pour la classe-signe elle-même » (Braithwaite 1992 [1962] : 18). Et un peu plus loin, il est montré que la formule v Gen r(v), n’ayant pas de variable libre, « on peut considérer qu’elle exprime la proposition que tout n’est pas une “preuve” de p(G)p, autrement dit que p(G)p est “improuvable” » (ibid. : 19).

           La raison pour laquelle Aristote considérait la preuve « per impossibile » comme le plus faible des modes d’inculcation de la preuve auquel on puisse recourir dans la démonstration scientifique (épistémè) est, comme nous l’avons vu dans la deuxième partie, son caractère doublement indirect : elle implique tout d’abord de tester une prémisse ex hypothesi, à titre hypothétique, puis d’examiner ses conséquences ; ensuite, si celles-ci débouchent sur une conclusion « impossible », d’adopter la contradictoire de la prémisse initialement envisagée. Ce qui affaiblit encore davantage ce mode de preuve, c’est que le syllogisme sous-jacent ne s’obtient pas sous sa forme finale pour des raisons positives mais uniquement négatives. La pauvreté du lien résulte bien sûr de la prémisse « inversée », où le contraire est aisément produit en lieu et place du contradictoire, voire pire encore lorsque la prémisse en question n’exprime pas une condition binaire de type « oui ou non » et qu’il existera plusieurs alternatives lorsqu’il s’agira d’« inverser » le contenu. 

          1. Je vous en prie Paul, c’est un plaisir de vous lire et relire (surtout cet ouvrage très important).

            PS – la prémisse inversée dans le cas de pair ou impair répond parfaitement à cette condition binaire évitant plusierus alternatives. Mais bon, ce sont là des mathématiques “inférieures”, bien loin de vos controverses avec vos pairs, cela dit sans faire d’impairs 🙂

  11. A toutes fins utiles, voici une thèse de philosophie en accès libre sur laquelle je suis tombé en cherchant des textes sur Perelman et Gödel. Je ne vais pas avoir le temps de creuser plus avant, mais peut-être ce travail est-il pertinent au sujet discuté ?

    “De quoi les ”théorèmes de limitation des formalismes” : théorèmes de Gödel de 1931 et apparentés, sont-ils la limitation?”
    Thèse de Patrice Pissavin soutenue en 2019

    “Nous cherchons à définir la nature des limitations révélées par les “théorèmes de limitation des formalismes” (Théorèmes de Gödel de 1931, de Church de 1936, et de Turing de 1936-1937) (…)”

    https://tel.archives-ouvertes.fr/tel-02493455/document

    1. Je viens de lire la conclusion de la thèse de Patrice Pissavin (il faudrait tout lire bien entendu : cela semble très bien fait). On perçoit une sympathie “pro-Hilbertienne” (rejet de l’intuition, des boîtes-noires, etc.) du même type que la mienne (on peut me considérer comme un pro-Hilbertien extrémiste, ça me convient), mais on lit surtout (le style de la thèse y pousse), un souci de ne fâcher personne. Le passage suivant me semble à retenir pour un futur traité de l’art diplomatique 😉 :

      Quant à ce que l’auteur pense des critiques de Perelman, Guilbaud et de moi-même (sur leurs épaules de géants…), impossible de le savoir : nous n’apparaissons pas dans son texte.

      1. La diplomatie ça doit être de l’esprit de finesse , dans NP, et la ” logique” de la cohabitation des états conduit sans doute à ce que toute vérité n’est pas bonne à dire . Encore une histoire de temps donné au temps .

      2. Medellín, le 28 février 2021

        @Paul Jorion

        * Puis-je vous recommander de (re-)lire cette entrevue avec Dirk Jan Struik (1989).

        https://www.ocf.berkeley.edu/~lekheng/interviews/DirkStruik.pdf

        * Ce qui me frappe dans la these de Pissavin (au moins sur mon laptop) est le manque de la fonction de recherche (f3) dans le texte.
        (néanmoins, je suis heureux de retrouver le nom de mon prof de math Anne T. dans sa bibliographie, au moins un, tout petit, lien au travail de l’institut Freudenthal..).

        * Ce qui est completement in-imaginable pour moi: Pissavin ne mentionne pas du tout a Ehrenfest dans sa these, et (alors ou pas alors ?), il ne mentionne non plus a Tinbergen (mieux dit: aux Tinbergens), ni a Bloembergen, ni a (Martin) Veldman… parfois on se demande qu’est-ce qui passe en France, on oublie simplement les Dirk Jan Struik, les Paul Jorion?

        Ou cela fait-il également partie de la diplomatie en France?

        😉

        1. Pour Paul Jorion , c’est pour qu’on ne l’oublie plus qu’il s’est installé à Vannes , et qu’il a conservé le français comme langue de la diplomatie .

  12. Pourrait on faire un parallèle entre “P vs NP ” et “intelligence inductive vs intelligence déductive” ( voire ” intelligences multiples” chères à Howard Garner , ou “esprit de finesse vs esprit de géométrie” cher à Blaise ) ?

    Bon , reste à poser l’axiome concernant ” l’intelligence” .

    Restons en aux bonnes règles pour conduire un raisonnement ” juste” , en essayant de ne pas trahir Aristote , et c’est déjà assez exigeant .

  13. Une manière rigolote de regarder le problème consiste à poser la question, existe-il une famille d’algorithmes dont la “complexité moyenne” est P qui est une solution pour chaque problème NP ?
    Est-ce-que un formalisme mathématique permet de modéliser n’importe quel problème que l’humanité désire résoudre?
    Comment savoir si un problème est bien posé ?
    A qui profite le secret ?
    Est-il possible de comprimer du bruit parfait (donc pas réel) sans perte d’information ?

  14. Une question : avons-nous , à ce jour, une description d’un phénomène de la physique dont l’explication passe par l’utilisation de l’infini cantorien (lequel, selon mon entendement, est une très grosse bévue linguistique, par mélange de niveaux de signifiant, pour n’être rien d’autre que la version débilitante du paradoxe du menteur) ?

    Pourtant, les processus naturels peuvent mélanger les niveaux d’abstraction linguistique, au sens ou un niveau inférieur de niveau N envoie, à l’insu de son plein gré , des signes de son activité que le niveau supérieur. N+1 utilise pour réguler le niveau N. Pour le dire autrement le vivant est récursif par construction (et peut être même l’univers, au sens de l’impédance itérative de tout phénomène électromagnétique , c’est-à-dire que si vous faite tourner une dynamo quelque part , dès lors que vous allumer une lampe qui y est branchée ailleurs , la dynamo en est informée et s’adapte son régime ( c’est un principe, très général , qui fut formulé par Albert Ducroc dans sa Théorie générale des systèmes et des effets.

  15. Bonsoir…
    @ P.J.
    Lorsque, dans votre vidéo, vous parlez d’une mathématicienne ça m’a rappelé une amie que j’avais rencontré à Tanger entre 1992 et 93.
    Avec qui nous avions un peu parlé d’IA, d’ailleurs…
    Si par hasard…
    Car je ne sais pas ce qu’elle est devenue, elle s’appelait Sophie, et c’était bien le genre à s’attaquer à des problèmes aussi bizarres que passionnants comme votre “P (±/=/≠ ?) NP”.

    @ Olivier.P
    Merci de nous avoir joint la vidéo de David Louapre : je n’ai sûrement pas tout compris du premier coup, mais j’y retournerai, et je pense/j’espère avoir un peu mieux cerné le sujet.

    Bonne soirée @ tous !

  16. Total désaccord sur votre remise en cause de la preuve par l’absurde. Et surtout sur vos arguments, plutôt café du commerce, pour cette remise en cause: on peut exprimer le contraire d’une proposition, pas d’un animal (girafe à nez vert, ou je ne sais plus). Je vais lire plus attentivement, en particulier, les pages que vous citez (de “comment la vérité….”), mais mon sentiment est que vous vous aventurez hors de votre champ de compétence.
    Les résultats de Gödel sont considérés comme acquis par la plupart des mathématiciens. Je suis bien conscient qu’il s’agit d’un argument d’autorité. Mais sur la preuve par l’absurde, vous remettez en cause le concept même de contraire d’une proposition, ça me semble pas sérieux.

    1
    1. Non, il ne s’agit pas du café du commerce ou d’incompétence de ma part, il s’agit d’un débat classique entre mathématiciens, où je suis conscient de me situer dans un camp particulier : celui de l’empirisme critique. Cf. Ladrière (1957) : “… l’attitude empiriste, qui considère l’être mathématique comme le produit d’une activité et ne lui attribue de réalité qu’à l’intérieur de la loi de construction qui permet de l’atteindre […] Pour l’empiriste, un système formel n’est qu’une description provisoire des procédés de construction admis à un moment donné de l’histoire de la science” (Les limitations internes des formalismes. Étude sur la signification du théorème de Gödel et des théorèmes apparentés dans la théorie des fondements des mathématiques, pages 31-32).

      Que vous preniez ce que je dis ou écris à ce sujet pour du café du commerce ou de l’incompétence de ma part, me fait comprendre en tout cas, et à tous ceux qui nous lisent ici, que ces débats sur les fondements des mathématiques ne vous sont pas très familiers.

      1
    2. “Il existe 2 grandes attitudes correspondant à une dualité des conceptions des savoirs mathématiques. D’une part l’attitude platonicienne qui considère l’être mathématique comme existant en soi, indépendamment des procédés par lesquels on l’atteint, procédés considérés comme indicateur d’existence”. D’autre part les empiristes comme Jorion. Ça pose évidemment un problème dans le champ du genre : est-ce que les femmes sont l’absurde des hommes ou le contraire ? quels sont les indicateurs d’existence des unes et des autres, quand l’Être pour sûr y rabat son caquet.

Les commentaires sont fermés.