P=NP sondage

[amineyasmine]

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 ?
-----

[pm42]

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 )

[amineyasmine]

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

[gg0]

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.

[A voir en vidéo sur Futura]

[Médiat]

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

[pm42]

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

[Médiat]

Et sans oublier la Bill 246 de l'Indiana

[pm42]

Et sans oublier la Bill 246 de l'Indiana

Oui, c'était un grand moment aussi.

[invite7b7f1ad0]

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

[Deedee81]

Salut,

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)

[pm42]

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.

[Deedee81]

Salut,

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).

[Deedee81]

Salut,

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 )

[pm42]

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.

[Deedee81]

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

[pm42]

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.

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.

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.

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.

[Deedee81]

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)

[invite44510b00]

(*) 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).

[amineyasmine]

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 ?

[Deedee81]

ce serait ou il est ?

Excuse-moi mais cette phrase est incompréhensible !!!!

[amineyasmine]

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 .....)

[Deedee81]

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

[Deedee81]

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é

[amineyasmine]

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

[albanxiii]

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.