-
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.… Lire la suite…
-
Vidéo – Paul Jorion & Yu Li : Vers une méta-connaissance
Théorème de Gödel et P. vs. NP… Lire la suite…
-
Vidéo – P vs. NP : problèmes solubles et insolubles
Le monde physique n’est pas entièrement réductible à sa modélisation mathématique… Lire la suite…
-
Unilog 2022 – What makes a demonstration worthy of the name? by Paul Jorion
Texte de l’article qui a été présenté aujourd’hui par ma collègue Yu Li de l’Université de Picardie, au congrès Unilog 2022 qui se tient à Chania en Crète. À terme, ce texte servira de préambule à l’exposé que je suis en train de bâtir sur la conjecture P vs NP. Une esquisse en français du texte ici a déjà été publiée sur le blog : Que démontrent les mathématiciens, et le font-ils d’une manière digne de ce nom ?, le 5 mars 2022.
What makes a demonstration worthy of the name?
Paul Jorion *
* ETHICS – EA 7446, Université catholique de Lille, 60 Bd Vauban, 59800 Lille, FranceSubject: Foundations of mathematics
Cite as: https://www.pauljorion.com/blog_en/2022/04/09/unilog-2022-what-makes-a-demonstration-worthy-of-the-name-by-paul-jorion/… Lire la suite… -
Et pendant ce temps-là… P vs. NP, le 28 mars 2022 – Retranscription
Retranscription de Et pendant ce temps-là… P vs. NP, le 28 mars 2022. Bonjour, nous sommes le lundi 28 mars…
Vous devez être connecté pour lire le contenu complet de l’article. Vous pouvez vous abonner ici… Lire la suite…
-
Vidéo – Et pendant ce temps-là… P vs. NP
Me faire comprendre, même des …. mathématiciens… Lire la suite…
-
Vidéo – P vs. NP – Premières réflexions, le 3 janvier 2021 – Retranscription partielle
Non, ce n’est pas une erreur : il s’agit bien d’une vidéo datant d’il y a un an, que je ne vous ai pas montrée à l’époque. Si je vous la montre aujourd’hui, c’est que je suis en train en rassembler tout ce que j’ai à dire sur la conjecture P vs. NP.
De premières réflexions, précédées du sujet à propos duquel Yu Li m’avait contacté : « Un cheval blanc n’est pas un cheval », paradoxe classique proposé par le dialecticien chinois Gongsun Long [env 320–250 av. J-C]. Vous trouverez ici le texte que j’avais consacré à cela sur le blog : Un cheval blanc (chinois) n’est pas un cheval, le 5 avril 2007
La retranscription ne reprend que la deuxième partie : celle qui parle de P vs.… Lire la suite…
-
Qu’est-ce qu’une démonstration digne de ce nom ?, le 25 août 2021 – Retranscription
Retranscription de Qu’est-ce qu’une démonstration digne de ce nom ?, le 25 août 202. Bonjour, nous sommes le mercredi 25 août…
Vous devez être connecté pour lire le contenu complet de l’article. Vous pouvez vous abonner ici… Lire la suite…
-
Vidéo – P vs NP – Deuxième épisode
Et si le programme de Hilbert tenait toujours ?
(Et si Gödel, Church, Turing, Kleene avaient été de mauvaise foi ?)… Lire la suite… -
P vs. NP, le 27 février 2021 – Retranscription
Retranscription de P vs. NP, le 27 février 2021. Bonjour, nous sommes le samedi 27 février 2021 et aujourd’hui, je…
Vous devez être connecté pour lire le contenu complet de l’article. Vous pouvez vous abonner ici… Lire la suite…
-
Vidéo – P vs. NP
Pourquoi s’intéresser à cette conjecture mathématique ?… Lire la suite…