Moi et P=NP

3 participants

Aller en bas

Moi et P=NP Empty Moi et P=NP

Message 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".

Revenir en haut Aller en bas

Moi et P=NP Empty Re: Moi et P=NP

Message 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 ?
réponse:
tim9.5
tim9.5

Messages : 451
Date d'inscription : 18/10/2014

Revenir en haut Aller en bas

Moi et P=NP Empty Re: Moi et P=NP

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

Invité
Invité


Revenir en haut Aller en bas

Moi et P=NP Empty Re: Moi et P=NP

Message 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? Very Happy
tim9.5
tim9.5

Messages : 451
Date d'inscription : 18/10/2014

Revenir en haut Aller en bas

Moi et P=NP Empty Re: Moi et P=NP

Message par Invité Ven 6 Mai 2016 - 12:40

Si, mais un peu d'humilité c'est la base là dedans...

Invité
Invité


Revenir en haut Aller en bas

Moi et P=NP Empty Re: Moi et P=NP

Message 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".

Revenir en haut Aller en bas

Moi et P=NP Empty Re: Moi et P=NP

Message 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.
tim9.5
tim9.5

Messages : 451
Date d'inscription : 18/10/2014

Revenir en haut Aller en bas

Moi et P=NP Empty Re: Moi et P=NP

Message 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
Badak

Messages : 1230
Date d'inscription : 02/12/2011
Localisation : Montréal

Revenir en haut Aller en bas

Moi et P=NP Empty Re: Moi et P=NP

Message 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é


Revenir en haut Aller en bas

Revenir en haut


 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum