Médaille Fields

grolapinos dit:
Rasputin dit:
scand1sk dit:Accessoirement, si jamais P=NP, ça doit faire tomber à peu près tous les algorithmes de cryptographie développés à ce jour…

Un peu caricatural non ?

Je ne me rends pas compte de la palette de méthodes de cryptographie qui seraient bouleversées par ça.
Pour la plus connue d'entre elles à base de nombres premiers et de restes chinois, il me semble qu'on sait depuis pas longtemps que le test de primalité est dans P. Ça n'a pas encore bouleversé le monde. Globalement, même si on découvrait un algorithme en temps logarithmique, j'ai l'impression (mais je peux me gourrer sévère) qu'il suffirait de prendre des nombres premiers (beaucoup) plus grands pour faire tourner le bouzin.


Pour RSA, il faut factoriser un nombre, ce qui est plus difficile que de trouver s'il est factorisable.

Il me semble que les problèmes dans P ou NP doivent être répondalisationables par vrai ou faux, ce qui fait que factoriser ne serait dans aucune des deux catégories.
Rasputin dit:
scand1sk dit:Accessoirement, si jamais P=NP, ça doit faire tomber à peu près tous les algorithmes de cryptographie développés à ce jour…

Un peu caricatural non ?
Ben non, si P=NP, ça signifie qu'on est capable de résoudre un problème NP en temps raisonnable avec certitude, et qu'on l'a démontré.

Ben, temps raisonnable, déjà, c’est fortement contestable… Temps polynômial ne veut pas dire temps faible. Et s’il existait des algorithmes quadratiques pour la résolution de certains problèmes NP-complets, j’ai vaguement tendance à penser qu’on les aurait déjà trouvés, donc faut pas s’attendre à avoir d’un seul coup des complexités ridicules pour ces problèmes. Si “en temps polynômial” signifie “en theta(n^70)”, on n’a pas gagné grand’chose.

Si P=NP, j’ai l’impression quand même que ce sera plus un joli résultat théorique qu’un résultat vraiment concret. Mais de toute façon, qui pense que P=NP ?

VictorVVV dit:Il me semble que les problèmes dans P ou NP doivent être répondalisationables par vrai ou faux, ce qui fait que factoriser ne serait dans aucune des deux catégories.


J'ai un gros doute là-dessus, mais comme je suis pas spécialiste, j'attends d'avoir les avis des experts

Ce qui me fait réagir, c’est que cet argument sur la cryptographie est utilisé plus que de raison dans les articles relatés “P=?NP” pour rendre l’enjeu “sexy”.

Et comme le note, grolapinos, temps polynomial ne signifie pas temps “raisonnable”.

grolapinos dit:Mais de toute façon, qui pense que P=NP ?


P != NP, c'est l'axiome qui permet de supposer que les algos de cryptages sont sécurisés.
Et tu sais mieux que moi que démontrer qu'un axiome est vrai ou faux est un défit pour tout mathématicien !

Si le problème de factorisation est polynomial, c'est qu'on a trouvé un algo en temps constant. ça veut dire que si on dispose d'une machine suffisamment puissante, on est capable de décoder une clé en temps raisonnable (ce qui n'est pas le cas avec un algo non polynomial).

Après, c'est de la théorie. Mais si théoriquement possible, je connais plus d'un gouvernement qui chierai dans son froc (ça veut dire, théoriquement plus de secrets).

EDIT : ce post contenait des idées fausses sur les ordinateurs quantiques, je le supprime pour éviter de diffuser des erreurs.

grolapinos dit:
VictorVVV dit:Il me semble que les problèmes dans P ou NP doivent être répondalisationables par vrai ou faux, ce qui fait que factoriser ne serait dans aucune des deux catégories.

J'ai un gros doute là-dessus, mais comme je suis pas spécialiste, j'attends d'avoir les avis des experts


Je m'auto-cite : si tu veux factoriser l'entier n, et que tu considères comme instances de ton problème des couples de type (n,p) avec p premier, une réponse "vraie" de ton algorithme te donne une factorisation. Donc factoriser est bien un problème NP. Pour la classe P, on ne sait pas.

EDIT : là encore, je me corrige pour la toute dernière partie de mon assertion.
grolapinos dit:Sauf erreur de ma part, l'ordinateur quantique, qui va peut-être voir le jour dans les décennies à venir, est censé résoudre les problèmes non-déterministes en temps polynômial, et là, pour le coup, on est dans la vraie petite complexité puisque grosso-modo, le non-déterminisme repose en général dans le choix, donc c'est globalement du quadratique pour la plupart des problèmes NP-complets.

:shock:

...c'est pas faux.
Tiberias dit:
grolapinos dit:Sauf erreur de ma part, l'ordinateur quantique, qui va peut-être voir le jour dans les décennies à venir, est censé résoudre les problèmes non-déterministes en temps polynômial, et là, pour le coup, on est dans la vraie petite complexité puisque grosso-modo, le non-déterminisme repose en général dans le choix, donc c'est globalement du quadratique pour la plupart des problèmes NP-complets.

:shock:
...c'est pas faux.


:lol: :lol: :lol:

Oui, bon, ben hein, on n'est pas non plus obligé de lire les discussions de spécialistes (et je ne suis absolument pas spécialiste) :pouicboulet:
grolapinos dit:
Mais de toute façon, qui pense que P=NP ?


Moi, si N=1 :mrgreen:

Oui, oui, je sais :
:arrow:

En gros, N=NP, on pourrait le traduire comment.

Nan, paske j’aime bien les maths, mais là, je suis un peu largué… :oops:

A dit:
grolapinos dit:... la définition "naturelle" d'un nombre premier doit exclure 1 de la liste.

c'est quand meme dur d'exclure un des membres fondateurs des mathematiques... :oops:
A


:lol: :lol: :lol:
loic dit:
grolapinos dit:
Mais de toute façon, qui pense que P=NP ?

Moi, si N=1 :mrgreen:
Oui, oui, je sais :
:arrow:
je me demandes bien pourquoi on n'y a pas pensé plus tôt !!!

:pouicintello:
Triz dit:En gros, N=NP, on pourrait le traduire comment.
Nan, paske j'aime bien les maths, mais là, je suis un peu largué... :oops:


C'est P=NP, soit à squ'on dit... :D
Triz dit:En gros, N=NP, on pourrait le traduire comment.
Nan, paske j'aime bien les maths, mais là, je suis un peu largué... :oops:

P=NP
http://fr.wikipedia.org/wiki/Th%C3%A9or ... s#Classe_P (la classe NP est juste derrière)

JE PREVIENS : Y'a sûrement un bon nombre de conneries dans mon gloubiboulga vulgariste qui suit cet avertissement. C'est un mix entre mes souvenirs de cours et mes rafraîchissement via wikipedia. A corriger très certainement, donc.

En gros, tu as plusieurs "classes de complexité" des problèmes mathématiques pour définir le temps que ça va prendre à un ordinateur de le résoudre.
Tu es dans un problème "P" quand c'est compliqué mais que tu peux le résoudre pas l'application de force brute, c'est à dire en essayant toutes les combinaisons. En gros, ton problème se présente sous la forme d'un arbre raisonné dont tu vas parcourir toutes les branches (tu as un point de départ et tu te balades dans ton espace de solutions selon des règles. Prends les échecs : tu as une position de départ et tes possibilités sont limitées).
En gros, la complexité de ces problèmes est dite "polynomiale" parce que leur nombre de solutions est un chiffre porté à une puissance constante (très grande), voire un assemblage de ce type de trucs, à savoir, donc, un polynôme. (r.x^a+s.x^b+...)
Quand tu as un problème de classe "NP", c'est qu'il n'est pas déterministe même s'il est polynomial. Les problèmes P sont un sous-ensemble des problèmes NP, vachement plus durs à résoudre parce qu'il est pas possible de créer un bête arbre à parcourir, ou alors il y a une explosion numérique, je sais plus. De mémoire, le jeu de go est un problème NP. Tu peux pas faire comme aux dames ou aux morpions, tester toutes les solutions, pour le résoudre.
Bref, tu peux pas te fabriquer un big blue qui va tester toutes les combos pour gagner, parce que t'as pas la puissance nécessaire (et de loin) pour ce faire.
Bien sûr, c'est tant que tu restes dans le déterminisme. C'est-à-dire avec des algorithmes.

Les heuristiques sont là pour t'aider. En gros, tu cherche pas vraiment LA solution ultime, mais une solution utile, suffisante (en tout cas dans les problèmes d'optimisation complexes que j'ai eus à résoudre en cours).
Au lieu de tout essayer, tu te balades dans l'espace des solutions plus ou moins aléatoirement en espérant trouver une solution qui te va bien. Bien sûr, tu établis tout un tas de règles pour décider si la solution va bien, et quel chemin tu vas parcourir pour essayer de tomber dessus ;)

Si P=NP, alors en gros on peut tout résoudre sans trop de mal (i.e. dans un temps raisonnable). C'est juste qu'on sait pas forcément comment.
greuh
Triz dit:En gros, N=NP, on pourrait le traduire comment.


Je le tente...

En gros, on évalue les algorithmes à leur complexité. Imaginons un algorithme qui prenne une donnée de taille n pour rendre un résultat (par exemple, un algorithme qui trie une liste de n nombres en ordre croissant).

Cet algorithme a une complexité en temps linéaire si il fait un nombre d'opérations de l'ordre de kn pour donner le résultat, où k est une constante. Par exemple on peut imaginer un algorithme qui fait 3n opérations en gros. La complexité est quadratique si ce nombre d'opérations est de l'ordre de kn², et plus généralement polynomiale si c'est de l'ordre de kn^p.

Un problème appartient à la classe P s'il existe un algorithme en temps polynomial qui le résout.

Il appartient à la classe NP s'il existe un algorithme qui vérifie en temps polynomial que tel truc qu'on a déterminé autrement est bien une solution.

En gros, un problème de la classe P est un problème qui se résout vite. Un problème de la classe NP est un problème qui ne se résout pas forcément vite, mais si on "devine" autrement que tel truc doit être une solution, alors la vérification est rapide.

Il est clair que pour un problème qui se résout vite, ça va vite aussi de vérifier une solution, donc P est une sous-classe de NP. La question de l'inclusion réciproque est ouverte. Tout le monde pense qu'elle est fausse, mais on ne sait pas le prouver.

Si t'as rien compris, je laisse un autre t'expliquer s'il a le courage.

EDIT : partiellement grillé vu qu'on présente pas le problème tout à fait sous le même angle, c'est plutôt complémentaire.

Avant comme Loïc, je disais “1”… maintenant je dis “hein ?”… :kingboulet:

En fait, c’était juste pour le jeu de mot car les explications de Grolap’ sont à peu près très claires :lol:

L’explication de greuh est fausse.
Le plus célèbre des problèmes NP que l’on aimerait bien inclure dans P est SAT (satisfiabilité d’une formule logique). Et la c’est clairement un truc que l’on peut faire en force brute avec un arbre binaire.

Une intuition est de dire que les problèmes P sont ceux pour lesquels il existe un algorithme qui utilise un temps de calcul qui est un polynôme de la taille de l’entrée.

NP est utilisé pour les problèmes non déterministes polynomiaux. Une erreur répandue (mais intuitivement pas trop fausse) est de considérer qu’il s’agit des algos de complexité exponentielle (en gros si la taille de la donnée augment le temps est multiplié par un coefficient). Une vision plus juste est de dire qu’il s’agit de tous les problèmes que l’on peut résoudre par énumération des possibilités (avec le test de validité de chaque possibilité prenant une durée polynomiale).

Monsieur Bilbo dit:Le saviez-vous ?
Pourquoi n'y a-t-il pas de prix Nobel des mathématiques ?

La légende prétend qu'Alfred Nobel aurait refusé d'honorer les mathématiques pour éviter que le prix revienne un jour à Gosta Magnus Mittag-Leffler, un mathématicien qui lui avait volé le cœur de sa maîtresse Sophie Hess ! Ce n'est pourtant qu'une légende ; en effet Nobel n'était pas marié. Il a estimé que les mathématiques ne pouvaient « faire avancer l'humanité », ce qui était le but premier de ses prix.


En fait, il considérait les maths comme un outils pour la science et non comme une science. En fait, c'était un état d'esprit assez partagé à l'époque.