Bonjour,
C'est une info toute fraîche.
Le professeur Norbert Blum de Bonn (http://www.spektrum.de/news/loesung-...roblem/1494941) a déposé une proposition de preuve de 38 pages (https://arxiv.org/abs/1708.03486) selon laquelle P<>NP.
A suivre...
Cordialement.
fin du buzz, il vient de retirer sa preuve (faute de preuve) https://arxiv.org/abs/1708.03486
La voie ardue mais juste du révolutionnaire conservateur : bâtir en détruisant le minimum.
Salut,
En effet, c'est ce que je viens de lire sur ce lien : https://www.theregister.co.uk/2017/0...ils_yet_again/
Cela dit, faire la preuve théorique de P<>NP, c'est horriblement dur. J'ai l'impression qu'il faut en fait prouver qu'une approche (algo par exemple) qu'on ne connaît pas, n'existe pas ().
Cordialement.
Salut,
Dans plusieurs des problèmes du millénium, dont celui-là, dans la description, ils expliquent en substance qu'on a exploré toutes les pistes "simples" et que la solution va certainement passer par une approche nouvelle avec un détour par des outils mathématiques très différents (un peu comme la démonstration du grand théorème de Fermat qui passe par les courbes elliptiques, les mathématiques modulaires,...)Envoyé par Noress
Cela dit, faire la preuve théorique de P<>NP, c'est horriblement dur. J'ai l'impression qu'il faut en fait prouver qu'une approche (algo par exemple) qu'on ne connaît pas, n'existe pas (
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Salut Deedee,
Sur ce problème, le seul chemin possible (ce qui n'engage que moi) est de s'approcher d'une machine de Turing avec oracle, c'est-à-dire avoir l'ensemble des solutions dans l'abstrait à la manière d'une boîte noire. Mais lorsque sur Wikipédia, dans une approche intuitive il est "conseillé" de voir l'oracle comme un dieu, cela risque fort d'en refroidir plus d'un ou pire, de les faire basculer dans l'irrationnel.
L'oracle a une signification abstraite (même vu comme un dieu), il n'y a pas de problème.
Je ne suis pas spécialiste de P=NP, mais je fais confiance aux spécialistes quand ils disent qu'on ne trouvera la solution qu'en quittant le domaine de la complexité pour faire le lien avec d'autres domaines (qui peut deviner ? Topologie algébrique ou autres horreurs).
Il y a la même chose apparemment pour la conjecture de Riemann et (ça c'est pas dans le Millenium) la conjecture de Collatz. On peut à coup sûr le dire aussi pour la conjecture de Goldbach (pas le Millenium non plus) quand on voit les avancées actuelles (on est très proche de la solution !) qui utilisent des outils mathématiques extrêmement pointus.
En tout cas c'est à suivre
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Ah tiens, c'est disponible sur le net.
Description dans wikipedia, le plus avancé étant "Tout entier impair > 5 est somme de trois nombres premiers. Corollaire : résultat de Terence Tao, 2012."
Article : https://arxiv.org/pdf/1305.2897v1.pdf
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Ah oui, P<>NP est peut-être même indécidable dans ZFC ! Voir https://fr.wikipedia.org/wiki/Probl%....3DNP_dans_ZFC
Mais une bonne surprise n'est pas exclue.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Ho la vache, je viens de voir dans wikipedia anglais qu'il y a déjà eut 112 "preuves" publiées (pour égal ou différent) et toutes invalidées !!!!!!
Ca fait un sacré paquet !
P.S. désolé pour ce flood de quatre messages à la suite
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Salut,
L'affreux formaliste que je suis se demande pourquoi ce serait une bonne surprise que ce point ne soit pas indécidable.
Pour te rassurer, Cédric Villani a dit à peu près la même chose (sur France Inter), et depuis je hante les rues d'Orsay pour lui dire tout le mal que j'en pense
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
L'affreux formaliste que je suis se demande pourquoi ce serait une bonne surprise que ce point ne soit pas indécidable
Je voulais juste dire qu'on pourrait avoir une démo plutôt abordable. Dans wikipedia ils donnaient un exemple concernant un autre problème de ce type. Même si ici pour les différents problèmes cités cela parait peu plausible.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Ave Médiat,
Pour ma part, dans une conférence que je peux retrouver, C Villani a dit qu'il fallait sortir du formalisme. Sans me prononcer (hélas) sur le formalisme, cela m'a donné l'impression que sortir du formalisme c'est un peu comme s'aventurer dans le désert.Salut,
L'affreux formaliste que je suis se demande pourquoi ce serait une bonne surprise que ce point ne soit pas indécidable
Pour te rassurer, Cédric Villani a dit à peu près la même chose (sur France Inter), et depuis je hante les rues d'Orsay pour lui dire tout le mal que j'en pense
Cdt.
Salut Noress (j'ai bien aimé le "Ave Médiat"Pour avoir entendu plusieurs fois C Villani, je pense qu'il est profondément platonicien, ce qui est plus que courant dans sa spécialité (autant que c'est rare dans la mienne)
C'est étrange car je ressens l'inverse (désert étant pris comme métaphore d'un lieu de liberté et de potentiels).cela m'a donné l'impression que sortir du formalisme c'est un peu comme s'aventurer dans le désert.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Correction,
Il a exactement dit qu'"on sait pas s'il faut pas complètement sortir du formalisme" en ce qui concerne les satanés problèmes NP-Complets.
https://youtu.be/oPQKwE1I0E0?t=2882
Salut,
Je suppose qu'il fait référence à la fameuse conjecture P!=NP. En effet, si P=NP, peut-être faut-il aller "plus loin" pour pouvoir exploiter ça.
Mais si P!=NP, je vois mal comment sortir du formalisme résoudrait le problème.
Donc c'est peut-être ça son "on ne sait pas" (vu que c'est une conjecture)
Peut-on confirmer mes remarques/doutes ?
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Je n'ai pas compris votre remarque. C. Villani fait référence au problème de savoir si P = NP ou non.
En fait c'est bien ça que je pensais. Merci (je ne sais pas écouter la vidéo, pas de son).
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Ah ces Belges !
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Vous avez raison Médiat. J'avais tendance à voir le formalisme comme une sorte de sécurité dans cette tour d'ivoire évoquée dans une conférence de et par Pierre Cartier qui est pour moi le Yoda des Mathématiciens.
Alors est-ce que sortir du formalisme peut permettre d'y revenir et de l'enrichir, difficile de se prononcer quant on n'est pas du métier.
