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 ?
-----
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 ?
Il faut que la question soit poétique pour avoir une réponse positive
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.
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
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![]()
Et sans oublier la Bill 246 de l'Indiana
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
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![]()
Salut,
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)
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
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.
Salut,
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 à 06h59.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Salut,
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)
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
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.
Non, c'est clair, quand on a une clé aussi longue que le message on peut se demander à quoi ça sertEn 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 vivantCa 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 à 07h38.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
C'est expliqué dans la plupart des introductions à la cryptographie donc la liste des suspects pour ta lecture est grande.
Oui mais il faut l'infrastructure pour la crypto quantique. Mais effectivement, on sait qu'on trouvera des solutions.
De mémoire, on peut en casser certains mais pas tous.
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.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
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.
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)
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
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).
ce serait ou il est ?On ne fait pas de la science à coup de sondage ni à coup d'opinion. Ce serait donc contraire au point 6 de la charte.
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 à 09h13.
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![]()
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
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é![]()
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
effectivement il est bien le doc sur les classes de complexité
Not only is it not right, it's not even wrong!