Répondre à la discussion
Affichage des résultats 1 à 19 sur 19

Selon Norbert Blum, P<>NP

  1. #1
    Noress

    Selon Norbert Blum, P<>NP

    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.

    -----


  2. Publicité
  3. #2
    mmanu_F

    Re : Selon Norbert Blum, P<>NP

    fin du buzz, il vient de retirer sa preuve (faute de preuve) https://arxiv.org/abs/1708.03486
    Je sens une légère perturbation dans la Charte. -- Yoda

  4. #3
    Noress

    Re : Selon Norbert Blum, P<>NP

    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.

  5. #4
    Deedee81

    Re : Selon Norbert Blum, P<>NP

    Salut,

    Citation Envoyé par Noress Voir le message
    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 ().
    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,...)
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  6. #5
    Noress

    Re : Selon Norbert Blum, P<>NP

    Salut Deedee,
    Citation Envoyé par Deedee81 Voir le message
    (...)
    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.

  7. #6
    Deedee81

    Re : Selon Norbert Blum, P<>NP

    Citation Envoyé par Noress Voir le message
    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
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  8. #7
    Deedee81

    Re : Selon Norbert Blum, P<>NP

    Citation Envoyé par Deedee81 Voir le message
    quand on voit les avancées actuelles (on est très proche de la solution !) qui utilisent des outils mathématiques extrêmement pointus.
    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
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  9. #8
    Deedee81

    Re : Selon Norbert Blum, P<>NP

    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.
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  10. #9
    Deedee81

    Re : Selon Norbert Blum, P<>NP

    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
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  11. #10
    Médiat

    Re : Selon Norbert Blum, P<>NP

    Salut,

    Citation Envoyé par Deedee81 Voir le message
    Mais une bonne surprise n'est pas exclue.
    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

  12. #11
    Deedee81

    Re : Selon Norbert Blum, P<>NP

    Citation Envoyé par Médiat Voir le message
    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.
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  13. #12
    Noress

    Re : Selon Norbert Blum, P<>NP

    Ave Médiat,
    Citation Envoyé par Médiat Voir le message
    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
    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.

    Cdt.

  14. #13
    Médiat

    Re : Selon Norbert Blum, P<>NP

    Salut Noress (j'ai bien aimé le "Ave Médiat" )
    Citation Envoyé par Noress Voir le message
    C Villani a dit qu'il fallait sortir du formalisme.
    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)

    cela m'a donné l'impression que sortir du formalisme c'est un peu comme s'aventurer dans le désert.
    C'est étrange car je ressens l'inverse (désert étant pris comme métaphore d'un lieu de liberté et de potentiels).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  15. #14
    Noress

    Re : Selon Norbert Blum, P<>NP

    Correction,
    Citation Envoyé par Noress Voir le message
    (...) C Villani a dit qu'il fallait sortir du formalisme(...)
    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

  16. #15
    Deedee81

    Re : Selon Norbert Blum, P<>NP

    Salut,

    Citation Envoyé par Noress Voir le message
    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.
    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 ?
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  17. #16
    Merlin95

    Re : Selon Norbert Blum, P<>NP

    Je n'ai pas compris votre remarque. C. Villani fait référence au problème de savoir si P = NP ou non.

  18. #17
    Deedee81

    Re : Selon Norbert Blum, P<>NP

    Citation Envoyé par Merlin95 Voir le message
    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).
    Tout est relatif, et cela seul est absolu. (Auguste Comte)

  19. #18
    Médiat

    Re : Selon Norbert Blum, P<>NP

    Citation Envoyé par Deedee81 Voir le message
    je ne sais pas écouter la vidéo
    Ah ces Belges !
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  20. #19
    Noress

    Re : Selon Norbert Blum, P<>NP

    Citation Envoyé par Médiat Voir le message
    C'est étrange car je ressens l'inverse (désert étant pris comme métaphore d'un lieu de liberté et de potentiels).
    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.

Discussions similaires

  1. Réponses: 4
    Dernier message: 05/10/2016, 19h56
  2. Composante selon un axe
    Par abdeslam87 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 19/08/2014, 08h49
  3. Projection de P selon x et y
    Par Ketur34 dans le forum Physique
    Réponses: 7
    Dernier message: 31/12/2012, 14h51
  4. 60000 selon la police, 300000 selon les syndicats
    Par jgiovan dans le forum Débats scientifiques
    Réponses: 60
    Dernier message: 23/10/2010, 13h09
  5. Réponses: 8
    Dernier message: 12/07/2005, 19h45