preuve que P != NP ?

Répondre
 
Partager Rechercher
Citation :
Publié par Mothra
* Ma methode essaye de calculer la vraie solution, mais en fait n'est pas vraiment polynomiale, elle prend un temps exponentiel, ou pire pour trouver la solution. Je la lance plein de confiance, j'attend, j'attend, j'attend... et elle ne terminera "jamais" (comprendre que si j'avais les 95 prochains milliards d'annees pour calculer, alors j'aurais la solution, mais c'est une bonne approximation de jamais).
Tut tut . Il y a des problèmes de la classe NP qu'on sait très bien résoudre avec des méthodes exactes, il faut juste que la taille de l'instance soit limitée.
Certaines instances typiques sont suffisamment petites pour être résolues sans trop de soucis (par exemple, le problème du voyageur de commerce tombe pour des tailles de plus en plus grandes, et une partie des applications du TSP peuvent désormais être résolues de manière exacte) alors que d'autres bloquent très rapidement et pour des instances ridicules (l'affectation quadratique bloque très rapidement alors que les instances qu'on souhaiterait résoudre sont généralement extrêmement grandes).
Ce point ainsi que le fait que les approximations (et leurs garanties) ne sont pas aussi aisées pour tous les problèmes fait que même avec la réduction des problèmes NP-complets, ces problèmes ne sont pas toujours comparables. En recherche opérationnelle, il y a des problèmes NP-complets "faciles" et des problèmes NP-complets "difficiles".

... Ok ce que tu dis est vrai, et je pinaille pour mettre en avant une discipline parfois un peu trop vite oubliée quand on parle de complexité théorique .
Citation :
Publié par Mothra
Il est en outre probable que si P=NP, alors EXP=NP (EXP est la classe de probleme de difficulte suivante, ou la recherche de la solution est NP, et ou la verification d'une solution donnee est aussi NP), etc.
En fait, c'est pas très probable mais évident : si tu prouves que NP=P, alors EXP = NP (puisque le problème dans EXP admet un certificat en NP qui en fait est un certificat en P, alors le problème est en fait dans NP, donc dans P) = P (puisque P=NP) et tu fais tomber en cascade toutes ces classes basées sur la complexité du certificat.
Lien direct vers le message - Vieux 17/08/2010, 18h18
Donc si j'ai bien compris pour prouver que P=NP il faut prouver que NP ou EXP est inclus dans P (L'inclusion réciproque n'est pas nécessaire non?)? (Je vois ça comme des ensembles)
Et réciproquement?


@orime oui c'est pour ça que je demandais si ce n'était pas nécessaire vu que cela me semblait trivial (Mais comme cela me le semble juste, j'ai préféré demandé).

Bon en tout cas, ça m'a l'air bien sympa et casse tête au possible comme branche (Me suis déjà posé la question comment optimiser les temps de calculs sur des trucs, comme des procédures mapple, c'est déjà affreux alors là :3).
Lien direct vers le message - Vieux 17/08/2010, 18h42
Citation :
Publié par Sharnt
Donc si j'ai bien compris pour prouver que P=NP il faut prouver que NP ou EXP est inclus dans P (L'inclusion réciproque n'est pas nécessaire non?)? (Je vois ça comme des ensembles)
Et réciproquement?
P est inclus dans NP, trivialement.
Si tu peux résoudre un problème en temps polynomial, tu peux aussi prouver qu'une solution est correcte en temps polynomial (puisqu'il te suffit de re-résoudre le problème pour ça)
Citation :
Publié par Sharnt
(Me suis déjà posé la question comment optimiser les temps de calculs sur des trucs, comme des procédures mapple, c'est déjà affreux alors là :3).
Hacker son code pour qu'il tourne plus vite, c'est juste de la cuisine de programmation.
Trouver des techniques de calcul pour réduire le temps de résolution c'est de la recherche opérationnelle, et on entrevoit déjà les enfers mathématiques, avec des pauvres thésards rôtissant à petit feu sur un sujet qu'il n'avaient pas bien sondé.
Par contre, la théorie de la complexité et la calculabilité, c'est carrément des matnématiques pures (avec les fourches, les cornes et les pactes infernaux. On y voit Chtuluu à tous les barbecues, l'été). C'est très compliqué et ça demande une formation mathématique complète et poussée, donc difficile à aborder simplement en rentrant dans le secteur par le côté informatique, même en faisant de la RO.

Oui, on me dit souvent que les informaticiens sont des matheux qui ont mal tourné. Je fais semblant de ne pas avoir entendu et je m'efforce de ne pas y réfléchir, pour préserver ma santé mentale.
Lien direct vers le message - Vieux 17/08/2010, 18h58
Diantre, tout le monde a l'air de trouver ça énorme. Y'en a qui comprennent rien à la chose comme moi ?

Si jamais un P exclamatif vaut un NP, ça change quoi ?
Lien direct vers le message - Vieux 17/08/2010, 20h56
Citation :
Publié par Rombo
Si jamais un P exclamatif vaut un NP, ça change quoi ?
Rien. C'est un des problèmes mathématiques les plus compliqués de notre temps, mais c'est déjà conjecturé depuis longtemps, donc les gens font comme si c'était déjà le cas.
Lien direct vers le message - Vieux 17/08/2010, 21h09
Citation :
Publié par cricri
tous
Ta formule est fausse c'est exp(i*Pi).

La ton truc fait a peu près 23.

@orime Je m'en doute bien, là je n'ai le niveau que pour me rendre compte de mon ignorance donc bon :/
Lien direct vers le message - Vieux 17/08/2010, 21h19
/hs

Citation :
Publié par mediapart, article d'orald
a cette époque, nous pouvions nous lancer dans des sujets risqués. Nous n'étions pas encore sous l'emprise de la bibliométrie, des modalités absurdes d'évaluation et de financement de la recherche que nous connaissons aujourd'hui.


Aujourd'hui, la situation a radicalement changé. Les métiers de la recherche ne sont plus attractifs. Les jeunes s'en détournent, nos masters recherche se sont vidés. Il est devenu trop périlleux de se lancer dans un sujet audacieux en thèse, car c'est prendre le risque de mettre trop de temps pour la terminer, de ne pas publier assez. Mieux vaut donc s'engager dans des voies mieux tracées, aux résultats plus sûrs, et pour lesquelles il est plus facile d'obtenir des financements sur appels à projets. C'est le contraire de ce qu'il faut pour avoir une recherche dynamique et qui fait vraiment reculer les frontières du savoir. Lors de l'ouverture du congrès international de mathématiques de 1998, david mumford, alors président de l'union mathématique internationale, avait écrit un article intéressant, dans lequel il se préoccupait de la tendance croissante des gouvernements à vouloir contrôler étroitement la recherche. Avec le gouvernement de nicolas sarkozy, nous sommes en plein dans la politique dénoncée par mumford.
Lien direct vers le message - Vieux 19/08/2010, 13h06
Bah, même si le mec se plante, si le boulot ets de qualité il peut apporter des pistes. Une grosse partie de la recherche scientifique consiste à essayer de péter les démonstrations du voisin. Les lois dont nous nous servons pour expliquer ce qui nous entoure sont celles qui résistent le plus longtemps.
Bon j'arrete avant que quelqu'un ne commence à parler de quantique.
Lien direct vers le message - Vieux 21/08/2010, 01h24
Citation :
Publié par Heathcliff
Exponentiel.

Non, ce n'est pas comme ça qu'il faut interpréter les choses. Tu devrais lire les liens de l'OP, ils expliquent qu'un problème P, c'est un problème dont la solution est facile (rapide) à trouver, alors qu'un problème NP, c'est un problème dont il est aisé de vérifier qu'une solution est correcte.

Les systèmes de sécurité, en gros, sont des problèmes NP: il y a des tas de combinaisons possibles sur un coffre-fort, mais la bonne combinaison ouvre tout de suite. S'il y a un moyen (et ce moyen serait exposé si P = NP est prouvé de façon constructive) de trouver la combinaison sans toutes les tester, alors on peut tout briser facilement. Y compris les codes bancaires de n'importe qui, toussa. La fin du monde industrialisé <o/ (bon, c'est un peu exagéré).

Et puis, en programmation, "faire comme si" n'existe pas vraiment: mets-toi à la place d'un pirate, tu dis comment à ton programme de faire comme si P = NP? Assume(P=NP) ?
Ah merci ca m'éclaire.

Par contre j'ai du mal à voir à partir de quoi tu trouverais le code d'une CB, ou un mot de passe facebook (juste devant ton DAB, ou ton PC)
Lien direct vers le message - Vieux 21/08/2010, 15h19
Ce n'est pas à proprement parler le code de ta carte bancaire, c'est le cryptage qui permet l'échange d'information et l'authentification d'une personne.

Ici tu as un exemple de "dialogue" :
http://fr.wikipedia.org/wiki/Cryptog...ym%C3%A9trique

Ici un des algos les plus simples pour mettre en place une cryptographie.
http://villemin.gerard.free.fr/Crypto/RSA.htm

Ce n'est pas parce que demain, on démontre P=NP, même par une méthode constructiviste, qu'on aura forcément un problème au niveau des échanges. Tout dépendra des coefficients en jeu. On pourrait très bien trouver un polynôme qui soit pire que les méthodes actuelles niveaux bouffages de temps (par rapport au N utilisé actuellement). Cela signifiera juste qu'un jour, il y aura une frontière. Et que l'on devra alors se balader avec des tailles de clefs beaucoup plus grandes.
Lien direct vers le message - Vieux 21/08/2010, 16h20
Répondre

Connectés sur ce fil

 
1 connecté (0 membre et 1 invité) Afficher la liste détaillée des connectés
Thème visuel : Fuseau horaire GMT +2. Il est actuellement 06h13.
^^ Haut de page ^^