Discussion fermée
Affichage des résultats 1 à 25 sur 25

P=NP sondage



  1. #1
    amineyasmine

    P=NP sondage


    ------

    BSR

    Il y a eu plusieurs sondages sur le problème P=NP.

    c'est P diferent de NP qui gagne et j'ai pas aimé et je relance le sondage ici :

    Est ce que vous êtes pour P=NP ou P diferent de NP et pourquoi ?

    -----

  2. Publicité
  3. #2
    pm42

    Re : P=NP sondage

    Citation Envoyé par amineyasmine Voir le message
    c'est P diferent de NP qui gagne et j'ai pas aimé et je relance le sondage ici :
    Il y a presque une forme de beauté poétique quelque part dans cette phrase si on est très optimiste voire qu'on a abusé du pinard (pourtant je n'ai bu que 1 ou 2 verres de Nero d'Avola )

  4. #3
    amineyasmine

    Re : P=NP sondage

    Il faut que la question soit poétique pour avoir une réponse positive

  5. #4
    gg0
    Animateur Mathématiques

    Re : P=NP sondage

    Je sors d'un café philo sur le sujet "Changer d'opinion serait-il un indice d'intelligence ?" et on a vu que ce n'est pas si simple. Alors donner son opinion sur un fait mathématique étant par contre une preuve d'inintelligence, je ne répondrai pas à ce sondage.

  6. A voir en vidéo sur Futura
  7. #5
    Médiat

    Re : P=NP sondage

    J'ignorais qu'on pût faire des mathématiques à la majorité des sondés, l'avantage, c'est que compter des voix c'est plus facile que de démontrer
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  8. #6
    pm42

    Re : P=NP sondage

    Citation Envoyé par Médiat Voir le message
    J'ignorais qu'on pût faire des mathématiques à la majorité des sondés, l'avantage, c'est que compter des voix c'est plus facile que de démontrer
    Sauf si on est le parti démocrate américain organisant des primaires. Il ne faut pas sous-estimer la capacité des gens à faire n'importe quoi

  9. Publicité
  10. #7
    Médiat

    Re : P=NP sondage

    Et sans oublier la Bill 246 de l'Indiana
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  11. #8
    pm42

    Re : P=NP sondage

    Citation Envoyé par Médiat Voir le message
    Et sans oublier la Bill 246 de l'Indiana
    Oui, c'était un grand moment aussi.

  12. #9
    invite84127968

    Re : P=NP sondage

    Bonjour, il faut que je retire vite fait mes sous de la banque :

    Dixit wikipedia :

    "Position des théoriciens sur ce problème:
    Les théoriciens de la complexité algorithmique pensent en majorité que P ≠ NP. Dans une enquête réalisée par William Gasarch en 2002 auprès de 100 théoriciens de la question, 61 d'entre eux ont déclaré penser que P ≠ NP, alors que seul 9 d'entre eux pensent que P=NP, les 30 restants ne souhaitant pas prendre position sur la question, ou penchant plutôt pour l'indécidabilité dans ZFC. C'est d'ailleurs ce relatif consensus qui justifie l'emploi de la cryptographie à clé publique pour sécuriser les transactions bancaires. "


    Le coffre fort n'est donc pas sur à 100% mais entre 61 et 91% donc au mieux une chance sur 10 de tout perdre

  13. #10
    Deedee81
    Modérateur

    Re : P=NP sondage

    Salut,

    Citation Envoyé par Liet Kynes Voir le message
    Dixit wikipedia :
    Merci pour ce résultat.

    Ceci dit, je pense que faire un sondage sur P=NP est un problème NP (Non Possible sur Futura).

    On ne fait pas de la science à coup de sondage ni à coup d'opinion. Ce serait donc contraire au point 6 de la charte.
    Ta réponse clôt le sujet amha.

    Ceci dit, ce qui serait peut-être intéressant est des infos sur "l'état de l'art" dans ce domaine. Y a-t-il eut des progrès ? A-t-on démontré des versions plus faibles ? Approche-t-on du but ? Etc... (Perso je ne sais pas du tout, je n'ai pas suivi)
    Keep it simple stupid

  14. #11
    pm42

    Re : P=NP sondage

    Citation Envoyé par Liet Kynes Voir le message
    Le coffre fort n'est donc pas sur à 100% mais entre 61 et 91% donc au mieux une chance sur 10 de tout perdre
    Même demain on démontre que P=NP, il est parfaitement possible que la cryptographie à clé publique telle qu'on l'utilise aujourd'hui reste sure.
    Parce qu'on trouvera peut-être un algo polynomial pour factoriser les nombres premiers mais rien n'empêche que le degré du polynôme soit tellement élevé qu'en pratique, il faille des milliards d'années pour faire sauter un RSA.

    A court terme, l'algo de Shor est une plus grosse menace mais là aussi, le jour où on saura faire sauter le verrou de la cryptographie basée sur la factorisation des nombres premiers, on remplacera simplement par un verrou plus solide.

  15. #12
    Deedee81
    Modérateur

    Re : P=NP sondage

    Salut,

    Citation Envoyé par pm42 Voir le message
    on remplacera simplement par un verrou plus solide.
    Et ça existe déjà : https://fr.wikipedia.org/wiki/Crypto...post-quantique

    On n'aura donc même pas besoin de passer à la cryptographie quantique, très efficace (*) mais techniquement difficile à implémenter pour des raisons hardware.

    (*) Il y a plus sûr : les algorithmes de cryptographie symétrique. Certains sont en béton armé.
    Mais pas toujours bien adapté aux usages sur internet. Il faut échanger une clef (d'ailleurs c'est à ça que servirait la crypto quantique)
    Et le plus sûr de tous, strictement incassable : le maque jetable.
    Mais bon, utilisable dans des conditions très particulières (le téléphone rouge fonctionne ainsi ! La clef étant transférée par valise diplomatique).
    Dernière modification par Deedee81 ; 28/02/2020 à 07h59.
    Keep it simple stupid

  16. Publicité
  17. #13
    Deedee81
    Modérateur

    Re : P=NP sondage

    Salut,

    Citation Envoyé par amineyasmine Voir le message
    c'est P diferent de NP qui gagne et j'ai pas aimé
    Notons que l'opinion générale découle du fait que :
    - Avec les énormes progrès en algorithmiques
    - Après les tentatives d'améliorer des algorithmes NP
    On finit par se dire : "bon, rien à faire, ça marche pas. P est probablement différent de NP"

    De plus quand on voit certains problèmes NP complet : https://fr.wikipedia.org/wiki/Probl%C3%A8me_3-SAT
    (c'est le grand papa de ces problèmes, le premier à avoir été démontré comme tel)
    En cherchant un peu on se rend vite compte qu'il ne semble (le mot est important ) pas y avoir de meilleur approche qu'une approche combinatoire : on teste toutes les possibilités.

    Or Pour ce type de problème, le nombre de possibilités est N!. Et la factorielle est exponentielle.

    PECQFDMP (pas encore CQFD mais presque )
    Keep it simple stupid

  18. #14
    pm42

    Re : P=NP sondage

    Citation Envoyé par Deedee81 Voir le message
    Et le plus sûr de tous, strictement incassable : le maque jetable.
    Mais bon, utilisable dans des conditions très particulières
    Oui mais justement, le transfert sécurisé du masque est compliqué et si par hasard, on en a une copie, on peut tout décrypter facilement.
    Ce n'est pas vraiment une solution pour Internet et les transferts bancaires

    Mais le 1er lien que tu as donné est effectivement ce à quoi je faisais allusion et c'est très intéressant.

  19. #15
    Deedee81
    Modérateur

    Re : P=NP sondage

    Citation Envoyé par pm42 Voir le message
    Oui mais justement, le transfert sécurisé du masque est compliqué et si par hasard, on en a une copie, on peut tout décrypter facilement.
    Ce n'est pas vraiment une solution pour Internet et les transferts bancaires
    Non, c'est clair, quand on a une clé aussi longue que le message on peut se demander à quoi ça sert En fait ce n'est utile que dans ces cas très particuliers.
    J'ai même lu (sais plus où) que c'est le seul algorithme dont la sécurité absolue est démontrée

    Les protocoles symétriques sont tous très sûr et pour la plupart déjà "post quantiques" si on peut dire. L'idée est donc d'échanger une clef (raisonnable) par crypto quantique puis utiliser un protocole symétrique. Mais les protocoles asymétriques post quantiques rendront peut-être les choses plus faciles (la recherche est toujours en cours pour améliorer. Il y a d'ailleurs toujours beaucoup de recherches comme les algos permettant de faire certains calculs sur les données cryptées permettant ainsi, par exemple, l'élaboration de statistiques sur bases de données personnelles strictement protégées).

    Mais je dois avouer que moi ce que j'attends le plus c'est de pouvoir "casser" le NP avec le calcul quantique, pas pour la crypto, mais pour nombre de problèmes difficiles. J'espère encore voir ça de mon vivant Ca peut arriver plus souvent qu'on ne croit ces difficultés. Exemple, il y a une vingtaine d'année j'essayais de mettre au point une méthode de planification de tâches avec contraintes..... quand je me suis rendu compte que c'était NP complet (problème assez proche du problème du sac à dos), j'ai donc dû mettre en place un algo approché "plus ou moins satisfaisant". Aaaaah si j'avais eut un gros calculateur quantique à l'époque
    Dernière modification par Deedee81 ; 28/02/2020 à 08h38.
    Keep it simple stupid

  20. #16
    pm42

    Re : P=NP sondage

    Citation Envoyé par Deedee81 Voir le message
    J'ai même lu (sais plus où) que c'est le seul algorithme dont la sécurité absolue est démontrée
    C'est expliqué dans la plupart des introductions à la cryptographie donc la liste des suspects pour ta lecture est grande.

    Citation Envoyé par Deedee81 Voir le message
    Les protocoles symétriques sont tous très sûr et pour la plupart déjà "post quantiques" si on peut dire. L'idée est donc d'échanger une clef (raisonnable) par crypto quantique puis utiliser un protocole symétrique.
    Oui mais il faut l'infrastructure pour la crypto quantique. Mais effectivement, on sait qu'on trouvera des solutions.


    Citation Envoyé par Deedee81 Voir le message
    Mais je dois avouer que moi ce que j'attends le plus c'est de pouvoir "casser" le NP avec le calcul quantique, pas pour la crypto, mais pour nombre de problèmes difficiles. J'espère encore voir ça de mon vivant
    De mémoire, on peut en casser certains mais pas tous.

    Citation Envoyé par Deedee81 Voir le message
    Exemple, il y a une vingtaine d'année j'essayais de mettre au point une méthode de planification de tâches avec contraintes..... quand je me suis rendu compte que c'était NP complet (problème assez proche du problème du sac à dos), j'ai donc dû mettre en place un algo approché "plus ou moins satisfaisant". Aaaaah si j'avais eut un gros calculateur quantique à l'époque
    Je sais que des constructeurs automobiles font de la recherche sur des algos quantiques pour optimiser les trajets d'une flotte de véhicules autonome.

    La question n'est pas comment aller le plus rapidement d'un point A à un point B mais comment faire pour que des milliers ou plus de véhicules qui vont de n points vers m points fassent le trajet le plus efficacement donc sans créer de bouchons, etc.

  21. #17
    Deedee81
    Modérateur

    Re : P=NP sondage

    Citation Envoyé par pm42 Voir le message
    De mémoire, on peut en casser certains mais pas tous.
    Peut-être bien, mais pas les NP-complet en tout cas. On démontre qu'une solution polynomiale pour un problème NP-complet => une solution polynomiale pour tous.
    Ces problèmes étant courant (*) c'est une des raisons de l'intérêt de la conjecture.

    (*) mais y a pire
    https://fr.wikipedia.org/wiki/Th%C3%...h%C3%A9orique)
    Keep it simple stupid

  22. #18
    Fustigator

    Re : P=NP sondage

    Citation Envoyé par Deedee81 Voir le message

    (*) Il y a plus sûr : les algorithmes de cryptographie symétrique. Certains sont en béton armé.
    Certes, mais pendant près de 400 ans le problème de la distribution des clefs a été la difficulté principale, jusqu'en 1977 avec l’apparition de l'échange de clefs Diffie-Helmann (enfin en réalité 1969, comme on le sait depuis 2015).

  23. Publicité
  24. #19
    amineyasmine

    Re : P=NP sondage

    On ne fait pas de la science à coup de sondage ni à coup d'opinion. Ce serait donc contraire au point 6 de la charte.
    ce serait ou il est ?

  25. #20
    Deedee81
    Modérateur

    Re : P=NP sondage

    Citation Envoyé par amineyasmine Voir le message
    ce serait ou il est ?
    Excuse-moi mais cette phrase est incompréhensible !!!!
    Keep it simple stupid

  26. #21
    amineyasmine

    Re : P=NP sondage

    est ce que il est contraire au point 6 de la charte ou cela dépendra de l'évolution de la discution ( ce serait contraire .....)
    Dernière modification par amineyasmine ; 28/02/2020 à 10h13.

  27. #22
    Deedee81
    Modérateur

    Re : P=NP sondage

    Citation Envoyé par amineyasmine Voir le message
    est ce que il est contraire au point 6 de la charte ou cela dépendra de l'évolution de la discution ( ce serait contraire .....)
    Faire un sondage pour connaitre les "je pense que...." ou les "opinions", ce n'est pas scientifique.
    La réponse à "P=NP ?" ne pourra être connue que par une démonstration rigoureuse.

    Ceci dit, ici la discussion tourne jusqu'ici sur la complexité algorithmique et son usage. Ce qui est n'est pas hors charte.

    Concernant ta question :
    - Ici : https://en.wikipedia.org/wiki/P_vers...0_NP_or_P_=_NP
    Un passage expliquant pourquoi on aurait plutôt tendance à penser que P=NP ou que P!=NP
    - concernant la recherche sur ce sujet, il semble qu'on n'ait pas vraiment avancé
    - un article faisant l'état de l'art sur les classes de complexité : https://hal.archives-ouvertes.fr/hal-00948835/document
    Il devrait te plaire. Et il est en français
    Keep it simple stupid

  28. #23
    Deedee81
    Modérateur

    Re : P=NP sondage

    Et pour les "fausses" démonstrations, voir :
    https://www.win.tue.nl/~gwoegi/P-versus-NP.htm

    Certaines sont assez courtes : https://arxiv.org/ftp/cs/papers/0511/0511085.pdf

    Et on peut s'amuser à les déboulonner (celle là ce ne devrait pas être très difficile).
    Je me suis amusé à ça avec le grand théorème de Fermat il y a déjà longtemps.
    Mais bon, ça prend beaucoup de temps de faire ça, j'ai donné
    Keep it simple stupid

  29. #24
    amineyasmine

    Re : P=NP sondage

    effectivement il est bien le doc sur les classes de complexité

  30. Publicité
  31. #25
    albanxiii
    Modérateur

    Re : P=NP sondage

    Citation Envoyé par Médiat Voir le message
    J'ignorais qu'on pût faire des mathématiques à la majorité des sondés, l'avantage, c'est que compter des voix c'est plus facile que de démontrer
    Entièrement d'accord, ce fil n'a pas sa place ici.

    albanxiii, pour la modération.
    Not only is it not right, it's not even wrong!