Accueil
Évènements
Rechercher
S'enregistrer
ConnexionMoi et P=NP
3 participants
Page 1 sur 1
Moi et P=NP
par ☘fishcake☘ Ven 6 Mai 2016 - 5:27
____
Dernière édition par ☘fishcake☘ le Dim 20 Mar 2022 - 5:43, édité 1 fois
☘fishcake☘- Messages : 184
Date d'inscription : 15/09/2012
Localisation : le troisième trou a droit du panneau "la gauche est plus sûr".
Re: Moi et P=NP
par tim9.5 Ven 6 Mai 2016 - 11:08
Voici quelques idées qui me viennent à l'esprit.
Un problème NP-complet, c'est résoudre Candy Crush rapidement.
Le temps de résolution est essentiel à calculer, car pour être NP, il doit être exponentiel à la donnée initiale. C'est pourquoi il y a un grand investissement dans l'informatique quantique pour s'attaquer à ce type de problèmes. En effet, augmenter la mémoire et le processeur d'un ordi en mode binaire ne suffit pas pour les NP-problèmes.
Ce sont aussi des problèmes faciles à résoudre pour autant qu'on ait accès à une clef de départ. Dès que j'ai le premier nombre, je peux trouver aisément le second, par simple division.
La manière de formuler ton problème est importante : il y a toujours une solution ! Laquelle ?
Un problème NP-complet, c'est résoudre Candy Crush rapidement.
Le temps de résolution est essentiel à calculer, car pour être NP, il doit être exponentiel à la donnée initiale. C'est pourquoi il y a un grand investissement dans l'informatique quantique pour s'attaquer à ce type de problèmes. En effet, augmenter la mémoire et le processeur d'un ordi en mode binaire ne suffit pas pour les NP-problèmes.
Ce sont aussi des problèmes faciles à résoudre pour autant qu'on ait accès à une clef de départ. Dès que j'ai le premier nombre, je peux trouver aisément le second, par simple division.
La manière de formuler ton problème est importante : il y a toujours une solution ! Laquelle ?
- réponse:
- 1 fois le résutat !
En général on demande de travailler avec des nombres premiers. Sinon il suffit de tester des critères de divisibilité (par 2, par 3, par 5, etc) et le craking devient plus facile.
Un mathématicien théorique n'essayera pas forcément de résoudre le problème, mais se posera les questions suivantes : est-ce soluble ? en combien de temps ? peut-on le généraliser ? peut-on le classer dans un groupe de problèmes similaires ?
Par exemple, tous les problèmes NP-complet peuvent se réduire à un seul. Si quelqu'un donne une solution dans un temps humainement acceptable, les autres sont alors aussi résolus.
La méthode indienne est une méthode parmi d'autres pour multiplier deux nombres. Une calculatrice en utilise une autre pour trouver le résultat.
Le problème est plutôt la marche arrière. Je m'explique.
Mettre du lait dans du café est simple. La méthode pour y arriver est simple. C'est la marche avant. La marche arrière constiste à prendre du café au lait, et à séparer les deux entièrement. Avec 2 molécules mélangées, c'est facile. Avec 3, 4 aussi avec un peu de méthode qu'on peut généraliser.
Si c'est un pb NP-complet, on peut imaginer que le temps de résolution est de 2.7 fois 2 = 5.4 secondes pour deux molécules, ou 2.7 fois 2.7 fois 2.7. pour 3 molécules, mais 27000000000000000000000000000000000000000000 secondes pour 100 molécules seulement. (=e^100) Comme les ordis calculent "à l'aide de P en un temps exponentiel", le bug est là.
Exploser une tasse contre un mur est très facile à faire. Rassembler des millions de fragment pour trouver la tasse initiale (et le mur initiale) sans les connaître, c'est la marche arrière.
A mon avis, tu as intérêt à creuser la théorie NP-complet à fond, puis placer ton problème dans ce contexte dans les détails. Décrire entièrement la méthode (qui ne marche pas) avec une simple calculatrice pour bien comprendre les rouages.
Puis proposer le point de vue indien, et prouver que ça marche pour de petits exemples. Et finalement calculer le temps que ça prend pour l'exemple que tu as affiché, avec ta méthode. (Et arriver à un temps exponentiel, puisque c'est un problème NP-complet).
Heu, j'ai tout cassé, je crois (désolé
) Mais c'est aussi la force des maths de décrire correctement des problèmes, sans être capable de les résoudre.
tim9.5- Messages : 451
Date d'inscription : 18/10/2014
Re: Moi et P=NP
par Invité Ven 6 Mai 2016 - 11:39
Encore un génie incomprit qui en 3 lignes d'évidences va révolutionner des décennies de recherche de gens incomparablement plus compétent que lui...
Le coup du "c'est trop compliqué donc j'expliquerai pas", "je ne veux pas qu'on pique mon idée"... la base du troll scientifique...
Le coup du "c'est trop compliqué donc j'expliquerai pas", "je ne veux pas qu'on pique mon idée"... la base du troll scientifique...
Invité- Invité
Re: Moi et P=NP
par tim9.5 Ven 6 Mai 2016 - 11:47
L'écouteur est jeune. Il réfléchit dans son coin et a des idées. Ca prend du temps de comprendre que nos réflexions scientifiques ne sont qu'une goutte dans un océean, non? 
tim9.5- Messages : 451
Date d'inscription : 18/10/2014
Re: Moi et P=NP
par Invité Ven 6 Mai 2016 - 12:40
Si, mais un peu d'humilité c'est la base là dedans...
Invité- Invité
Re: Moi et P=NP
par ☘fishcake☘ Ven 6 Mai 2016 - 12:56
___
Dernière édition par ☘fishcake☘ le Dim 20 Mar 2022 - 5:43, édité 1 fois
☘fishcake☘- Messages : 184
Date d'inscription : 15/09/2012
Localisation : le troisième trou a droit du panneau "la gauche est plus sûr".
Re: Moi et P=NP
par tim9.5 Ven 6 Mai 2016 - 20:05
Cher écouteur de silences,
Si j'ai bien compris, ton principal problème est de le faire faire à un ordinateur. Dans ce cas, tu peux utiliser le pascal http://www.programmation-pascal.com/.
Effectivement, Hobb a un côté littéraire car il écrit souvent sur ce forum. Tu peux lire le fil sur les oscillations. J'en profite de le remercier pour ses messages qui vont droit au but, et souvent très condensés. Il faut les lire plusieurs fois pour bien comprendre ce qui est dit. Comme en poésie.
Si j'ai bien compris, ton principal problème est de le faire faire à un ordinateur. Dans ce cas, tu peux utiliser le pascal http://www.programmation-pascal.com/.
Effectivement, Hobb a un côté littéraire car il écrit souvent sur ce forum. Tu peux lire le fil sur les oscillations. J'en profite de le remercier pour ses messages qui vont droit au but, et souvent très condensés. Il faut les lire plusieurs fois pour bien comprendre ce qui est dit. Comme en poésie.
tim9.5- Messages : 451
Date d'inscription : 18/10/2014
Re: Moi et P=NP
par Badak Ven 6 Mai 2016 - 20:13
L'écouteur de silences a écrit:
hobb > bien sûr que je veux pas qu'on me pique mon idée. de toute façon j'ai donné un champ de possibilité pour pouvoir le résoudre je veux juste le faire avant ce qui me motive encore plus. et puis ça n'a rien de compliqué un mathématicien intermédiaires s'en sortirait avec ce type de résolution. Et le seul truc que j'ai pas dit c'est comment résoudre quand on a 3 chiffres. sérieux tu t'amuses à tourner le résultat dans tous les sens et tu arriveras au résultats toute façon. il suffit de prendre en compte des retenues comme tout calcul. je pense pas que c'est compliqué compliqué n'est pas là ce qui est compliqué c'est de le faire faire à un ordinateur. même quand je réfléchis un peu même si c'est la partie la plus compliqué je pense pas qu'elle ne sois pas résolvable. Je le répète il n'y a rien de compliqué. tu dois être plutôt littéraire parce que je vois pas ce que tu trouves de difficile là-dedans.
Désolé mais le problème de la factorisation, c'est compliqué. Puisque tu n'y trouves rien de compliqué, il se pourrait que tu te trompes.
En fait, juste prétendre que tu obtiens un algorithme en temps polynomial pour la factorisation, c'est douteux.
Je ne suis pas du tout spécialiste de la question, mais sur wiki, il est écrit que
L'ami wiki nous dit: a écrit: S’il peut être démontré qu'il est NP-Complet ou co-NP-Complet, cela impliquerait NP = co-NP. Ce serait un résultat très surprenant, par conséquent la factorisation entière est largement suspectée d'être en dehors de ces classes. Beaucoup de personnes ont essayé de trouver des algorithmes en temps polynomial pour cela et ont échoué ; par conséquent, ce problème est largement suspecté d'être également en dehors de P
Montrer que ton algortihme est dans P (si c'est le cas), ce n'est pas difficile en effet.
Tu peux prendre plusieurs ensembles de problèmes de taille croissante, et mesurer précisément la durée du calcul. Et ensuite faire le graphe de cette durée en fonction de la taille.
Mais il faut aussi faire attention à la quantité de mémoire: la mémoire doit aussi restée polynomiale. Si tu accélères les calcul en faisant exploser la mémoire nécessaire exponentiellement, ce n'est plus dans la classe P !!
Badak- Messages : 1230
Date d'inscription : 02/12/2011
Localisation : Montréal
Re: Moi et P=NP
par Invité Ven 6 Mai 2016 - 20:49
L'écouteur de silences a écrit:tim9.5 > Pense qu'on a besoin de trouver une seule possibilité possible mais on peut aussi faire un champ de possibilités et les comparer suffirait largement.
hobb > bien sûr que je veux pas qu'on me pique mon idée. de toute façon j'ai donné un champ de possibilité pour pouvoir le résoudre je veux juste le faire avant ce qui me motive encore plus. et puis ça n'a rien de compliqué un mathématicien intermédiaires s'en sortirait avec ce type de résolution. Et le seul truc que j'ai pas dit c'est comment résoudre quand on a 3 chiffres. sérieux tu t'amuses à tourner le résultat dans tous les sens et tu arriveras au résultats toute façon. il suffit de prendre en compte des retenues comme tout calcul. je pense pas que c'est compliqué compliqué n'est pas là ce qui est compliqué c'est de le faire faire à un ordinateur. même quand je réfléchis un peu même si c'est la partie la plus compliqué je pense pas qu'elle ne sois pas résolvable. Je le répète il n'y a rien de compliqué. tu dois être plutôt littéraire parce que je vois pas ce que tu trouves de difficile là-dedans.
Hé bien amuse toi avec les RSA720 qui tournent un peu partout sur le net alors... (PS : les gains obtenus en cas de factorisation ne sont plus acceptés depuis le PPMQ).
EDIT : la méthode qui est proposée ici, j'y ai déjà réfléchi, et en fait on reste en temps de calcul non polynomial (et mémoire non polynomiale non plus) : en gros, c'est pire que les méthodes existantes actuellement.
Invité- Invité
Page 1 sur 1
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum