Oui mais je ne sais plus le nom de la classe de complexité (il y en a pas mal donc...)Envoyé par ilelogique
Je comprend mieux ton approche. Ceci dit je pense que ça ne permet pas de savoir si ça aboutirait pour P=NP. Ca dépend des informations/algorithmes précis. Dans certains cas ça pourrait marcher (*) et dans d'autres non.
(*) Et vu le nombre de mathématiciens qui se sont penché sur le problème et sur les algos existant, j'ai de gros doutes. Mais rien ne t'empêche de chercher
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
merci
D'ailleurs si vous validez mon exemple cela voudra sans doute dire que c'est bien envisageable (comme déjà dit plusieurs fois, mon but n'est pas d'exhiber un tel ensemble E mais bien sa possibilité potentielle d'exister...)
donc je ne vais pas chercher, il me suffit juste de savoir si on peut envisager ou pas que ça soit possible (par exemple ne pas savoir la réponse fait qu'on peut envisager que ça soit oui...)
merci
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
Salut,
Non, ça ne permet pas de savoir si ça peut marcher. Tu ne peux pas extrapoler l'exemple donné aux problèmes NP-Complet. Je dis juste qu'on ne peut pas savoir si ça peut marcher ou pas.
EDIT et si ça marche, c'est une approche sans doute bien plus compliquée que les méthodes habituelles.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Ne serait-ce pas NP-difficile ?
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Pas sûr, peut être les {NP-difficile / NP-Complet} mais je n'en suis pas sûr.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
merci pour vos réponses, car pour vc j'ai du mal à voir qu'on puisse vérifier en temps polynomial mais bon, je peux le croire
Pour ce qui est de ma question, si vous validez mon exemple, je devrais pouvoir déduire que la réponse est "oui" à ma question (ma question n'est pas de savoir si ça peut marcher mais si on peut envisager, imaginer que ça puisse marcher, nuance...):
On peut bien envisager, à supposer qu'on ait prouvé P=NP et trouvé l'algorithme ad'hoc, de construire un ensemble E des Ai avec un ti pour chaque ensemble de i éléments de E et la suite t strictement décroissante et tn polynomial, même si, je l'admets c'est très improbable, me confirmez-vous bien svp qu'il n'est pas a priori impossible que ça soit faisable ?
D'ailleurs, vu qu'il existerait alors un plus petit i tel que ti soit polynomial il me paraît "facile" de créer les algorithmes en tj avec j<i, puisqu'il suffit pour ça de "gonfler" artificiellement l'algorithme en ti (en lui ajoutant de la complexité) non ? c'est plus pour les tj avec j>i (faire baisser le degré du polynôme) que ça paraît plus ardu
Si ça intéresse je peux aussi expliquer pourquoi je pose cette question mais bon
merci
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
Comme déjà dit je ne veux pas spécialement savoir si ça aboutirait mais si ça pourrait aboutir, s'il est concevable d'imaginer que ça aboutisse, petite nuance... merci
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
"concevable" ne veut rien dire : tout est concevable. Si ça n'aboutit pas, si on le démontre, alors il sera concevable à la fois que ça aboutisse (ça fait partie de l'idée) et que ça n'aboutisse pas. Le Père Noël est concevable, ainsi que l'idée que la lune est un gros fromage blanc.
Tout ça est du baratin sur une idée mal foutue, mais "concevable".
Tu as eu cette idée, elle était concevable. Elle ne sert à rien, pourquoi insistes-tu ?
Bonjour,
ok ggo a décidé d'être désagréable avec moi et après avoir enfoncé des portes ouvertes, désormais il joue sur les mots, c'est un tantinet fatiguant, je vois "animateur mathématique", je vous assure ggo, que vous n'êtes pas pédagogue pour deux sous en ce moment, le mépris ne mène à rien.
Ensuite, pour faire votre jeu de moralisateur : vous dites que ma question ne sert à rien ? Mais prouvez-le alors, vous ne savez même pas pour quelle raison je la pose ! Et si, oui, j'insiste, c'est juste que j'en attends une réponse (et selon moi on y est presque, le sujet est presque clos, et la réponse sera"oui" je pense).
Alors, pour le coup, ok, "concevable" n'est pas correct selon-vous, le souci, et je ne fais que vous citer ("tout est concevable") : mais à quoi donc peut bien servir le mot "concevable" si tout est concevable ? je vous remercie de me le dire...
je vais donc changer mon propos : ma proposition est-elle plausible, possible ? (et là vous ça vous conviendra peut-être, car, que je sache, si la quadrature du cercle est bien "concevable" (puisqu'elle le fût pendant des centaines d'années) elle est bien impossible)
Merci de ne pas aller hors sujet également...
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
Salut,
Du calme (à tous) ! ilelogique, faut quand même avouer qu'être satisfait "d'un truc qui pourrait marcher, peut-être, mais on ne sait pas et en fait probablement pas efficace pour peu que ça marche" c'est hummmmmm...... peu utile. Pas étonnant que gg0 ait bondit. Possible, plausible, concevable, tout ça c'est du même acabit. Ca ne mène nul part. Surtout en math ! Bon maintenant que tu as une idée "qui n'est pas idiote mais qui ne donne rien jusqu'ici", il faut que tu ailles plus loin et pas juste dire "je suis satisfait".
Exemple : je pourrais générer des algos aléatoirement. S'il en existe un P, je vais finir par tomber dessus. Est-ce que c'est plausible ? Oui, mais tel quel inutile et en pratique totalement irréalisable. Faut aller au-delà du plausible. Le plausible ça ne vaut pas grand chose. Si j'étais satisfait du fait que c'est plausible, franchement, je serais content de pas grand chose.
La seule chose sensée que tu pourrais maintenant faire est d'essayer de le mettre en pratique de manière concrète (et non plus abstraite et très vague). Donc lance toi. (pas ici sur Futura, mais sur papier et/ou en programmant des algos..., mais quand tu auras progressé fais-nous part de tes résultats, si tu le souhaites)
EDIT j'ai beaucoup joué à une époque avec des algos de toute sorte comme ça. C'est incroyable ce qu'on apprend en faisant ça. Donc, bonne exploration
Dernière modification par Deedee81 ; 24/08/2021 à 08h54.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Merci deedee81 pour votre modération.
néanmoins, au risque de vous décevoir, je persiste, comme je l'ai déjà dit de nombreuses fois je n'ai pas du tout besoin d'un truc concret mais bien d'une "possibilité, une plausibilité". D'ailleurs vous l'avez bien tous lu : dans ma question je pars déjà du principe qu'on a P=NP et l'algorithme ad'hoc, ce qui, en soi, est déjà plutôt irréaliste.
vous dites "franchement je serai content de pas grand chose", je comprends et vous avez bien raison, cela dit, je me contente de peu et c'est bien une chose comme ça, simplement, que j'ai besoin de savoir !! (que, tout simplement, ce n'est pas rigoureusement prouvé que c'est impossible et que donc c'est possible),
Et ça n'empêche pas (contrairement à ce qu'on m'a dit) qu'il y ait de la rigueur dans ma recherche "non rigoureuse" :
Si je vous avais demandé "est-ce que ça vous paraît possible d'imaginer un processus permettant, à la règle et au compas seulement, de construire un cercle d'aire égale à celle d'un carré donné ?" vous m'auriez sans aucun doute répondu (et de façon rigoureuse, avec une preuve) que la réponse est non, vu qu'on sait désormais que la quadrature du cercle est impossible.
Dès lors, de la même façon, je vous ai donné un exemple de ce que j'imaginais, du coup pour ma question P=NP, je n'ai pas besoin de quelconque algorithme, juste une éventuelle "infirmation" (comme pour la quadrature du cercle) me suffirait, et de déduire que mon problème est un problème ouvert me suffit amplement.
D'ailleurs du fait que j'ai donné un exemple qui me semblait marcher (avec l'algo de tri) et que personne n'a contredit (ce qui n'implique bien sûr pas que ça marche), j'en déduis qu'on "pourrait" procéder de même pour ma question P=NP (encore une fois, le fait que ça soit hautement improbable ne me gène pas du tout dès lors qu'il y a la moindre toute petite fenêtre de possibilité)
j'aurais juste bien aimé, pour clore ce sujet, que quelqu'un dise (en tout sincérité) par exemple un truc du genre "ce que tu demandes est hautement improbable mais pas complètement impossible", mais bon... si personne ne le pense...
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
vous dites peu utile, j'en conviens, mais pour moi c'est suffisamment utile je vous assure, voila
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
Et bien ma foi si ça te satisfait
Si on l'a dit c'est parce que tu as tout fait pour cacher cette rigueur. Je ne dis pas ça pour me moquer. Tes messages étaient incroyablement peu clair et brouillons. Alors peut-être que tu y vois de la rigueur mais aucune chance que les autres y voient de la rigueur ! N'oublie pas qu'on est dans le forum de math, si c'est rigoureux alors on peut poser un problème sans utiliser un seul mot (de la langue française) bien que ce serait chiant et aride de faire ça. Avec les messages précédents, les mettre sous cette forme..... bonne chance !
Ca on le savait déjà.
C'est juste qu'on n'en sait rien. On ne peut pas te donner une réponse qu'on n'a pas. Désolé !
Dernière modification par Deedee81 ; 24/08/2021 à 10h12.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
j'ai bien compris merci et oui ça me suffit, j'avais peur qu'on me dise que c'est impossible, donc si vous ne savez pas c'est bien que je peux l'envisager (aussi farfelu soit-il)
mes messages peu clairs oui j'en conviens, désolé, je ne cachais pas ma rigueur (j'en ai), mais je sais pourquoi je suis venu ici poser cette question et, en effet, elle s'est mieux clarifiée quand j'ai introduit mon ensemble E (là c'est devenu plus clair je pense non ?)
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
Personnellement, je ne vois toujours pas l'intérêt de la question, mixer des algorithmes revient à fabriquer un nouvel algorithme ; chaque algorithme pouvant être découpé en parties plus ou moins indépendante a la complexité de sa partie la plus complexe, donc je repose la question : à quoi ça sert ?
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
C'est pas tant l'ensemble en question qui a aidé, c'est juste ton message qui était plus facile à comprendre.
Mais je pense que le sujet est clôturé (enfin jusqu'à ce que le problème soit résolu, on attend le prochain Perelman)
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
ça sert à créer une sorte de chaîne d'algorithmes (imaginaires bien sûr vu que P=NP n'est pas prouvé) de complexité algorithmique décroissante en lien avec p=NP, en gros plus on trouverait d'Ai et plus on se rapprocherait de l'algo de P=NP, se rapprocher peu à peu d'algorithmes permettant, du coup, des puissances de calculs extrêmement efficaces
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
Oui mais quel intérêt de faire ça (étant donné que ce serait sans doute la méthode la plus inefficace au monde pour créer des algorithmes efficaces, voir ce que j'en disais plus haut). Est-ce que tu as déjà programmé des algorithmes un tant soit peu compliqués (pas pour P=NP mais pour quoi que ce soit) ? Par exemple des algorithmes avec pleins de boucles imbriquées (et qu'il faut accélérer) ? Si oui tu dois voir à quel point ta méthode serait inefficace. Sinon, le mieux est que tu essaies pour voir pourquoi ce n'est pas intéressant.
(un exemple : j'avais programmé le problème des huit dames avec huit boucles imbriquées..... une horreur.... j'ai alors optimisé et certainement pas mélangé avec un autre algorithme. Résultat de mon optimisation : une fraction de de seconde sur Vax). Autre exemple : optimisation de l'algorithme alpha-bêta (j'ai obtenu de bons résultats mais sur des cas assez simples).
Je suis d'accord que si tu es satisfait de la réponse c'est toi que ça regarde. Mais c'est pas pour cela qu'il y a un intérêt.
EDIT ah tiens, ça me rappelle un qui avait une idée pour programmer les nombres premiers et dont l'idée était sans doute l'algorithme le plus lent de tous les temps. Sais plus où j'ai vu ça.
Dernière modification par Deedee81 ; 24/08/2021 à 10h47.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
oui j'ai déjà fait un peu de programmation mais je ne suis pas informaticien donc sans doute pas aussi compliqué que ce que tu as fait toi.
l’intérêt est d'avoir une suite d'algorithmes (imaginaires bien sûr) de plus en plus efficaces qui tende vers un algo polynomial de bas degré pour P=NP
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
je fais de la vulgarisation scientifique (voir ici : www.ilelogique.fr) et une des idées consiste a expliquer (de façon rigoureuse!!!) le problème de P=NP mais je mets cela au sein d'une fiction dans laquelle un type aurait prouvé et trouvé l'algo pour p=np, la chaîne d'algo de complexité décroissante enrichit le côté dramaturgique (donc seulement besoin d'être plausible, pas forcément réaliste), comme des secrets cachés...
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
Ah, fallait le dire, que tu fais du roman ... et de la vulgarisation. Mais dans ce cas, le roman permet tout, et les vulgarisateurs, souvent, aussi. La vulgarisation du problème P=NP nécessite une certaine rigueur, des connaissances précises, pas seulement du "c'est concevable", qui noie le poisson.
A toi de voir quel vulgarisateur tu veux être.
Cordialement.
Jamais entendu parler de cet algorithme, le problème de N=NP est de trouver un algorithme P qui résoud un problème NP, et dans ce cas voir mon message #15
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
D'une manière générale on ne peut faire de la bonne vulgarisation que si on maîtrise (techniquement) le domaine concerné.
J'ai fait des vidéos sur la théorie des groupes.... mais il ne me viendrait pas l'idée d'en faire sur la topologie algébrique !!!!
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Abus de langage
Et pas mal d'autres. Il y en a plusieurs qui sont édifiant quant à la validité de l'idée.
Mais ma foi si c'est pour de la fiction
(je faisais un commentaire sur la vulgarisation... mais pas sur la sienne, je n'ai pas trouvé sur le site internet en question où on parle surtout de clowns).
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
ggo merci de bien lire svp : je compte vulgariser le problème de P=NP et cela de façon rigoureuse ça va de soi, ensuite ma chaîne d'algo ne servira pas à expliquer P=NP mais juste à créer de la dramaturgie (d'où juste la nécessité d'être plausible (même si quasi improbable)), si vous saviez le nombre de fois où j'ai expliqué (rigoureusement) des choses en me plaçant volontairement dans un environnement farfelu ! (théorème de Poincaré avec des gens qui rétrécissent quand ils s'approchent du bord, théorie des groupes avec des additions d'émotions ou des déplacements dans les duels (cf Evariste Galois), et autres suites qui déshabillent les filles pour expliquer la sensibilité au premier terme, ou un pays où les gens auraient leur taille proportionnelle à leur âge pour expliquer la proportionnalité etc.
mediat : quand je parle de l’algorithme de P=NP c'est bien celui dont tu parles, qui permettrait de résoudre un problème NP-complet en temps polynomial
Deedee81 : oui évidemment ça va de soi (et je pense maîtriser la question de P=NP) mais je n'ai pas besoin de connaître ni maîtriser l'algo P cité plus haut (et qui n'existe d'ailleurs pas à ce jour) car ce n'est pas de lui, ni de ma chaîne descendante dont je veux parler rigoureusement (encore une fois : juste besoin de plausible, c'est juste pour la dramaturgie)
oui je fais du clown, mais pour vulgariser rigoureusement les sciences abstraites et théoriques (la page de chaque spectacle ou prestation précise le contenu scientifique abordé), si ma façon de travailler vous intéresse, lisez mon livre (préfacé par Cédric Villani...), on trouve sur le site (A l'endroit de l'inversion, petit essai en clownologie mathématique)
vous pouvez aussi lire ceci, qui est plus succinct.
En tous cas merci à tous pour vos réponses (et même ggo va !)
je crois que le sujet est donc clos, merci
et si vous voulez suivre L'île logique, contactez moi par le formulaire de contact du site et je vous ajouterai à ma liste de diffusion (un mail tous les 3 mois environ)
bien à tous et merci
Dernière modification par ilelogique ; 24/08/2021 à 12h00.
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
Mais ce n'est pas possible de finr ainsi, te diras auguste , tu as choppé les mots croisés comme sur google (https://www.google.com/search?q=pr%C...h=684&dpr=1.25) ?
Vous êtes inspirés de la même façon que Villeret dans https://fr.wikipedia.org/wiki/Effroyables_Jardins ?
Sans questions il n'y a que des problèmes sans réponses.
Moi je veux bien continuer de dialoguer et parler de mon sujet des Ai et ti mais je ne veux pas encombrer l'espace ni le temps non plus !
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
Et je crois que je me suis inspiré tout seul, ou disons de mon entourage propre.
S'il n'y avait pas de vérité absolue, "toute vérité est relative" en serait une
SAT∈NP-complet⟹∀L
Théorème de Cook-Levin
Ce théorème est fondamental pour
P=NP car il a introduit la notion de NP-complétude. Il affirme que le problème de satisfiabilité booléenne (SAT) est NP-complet
NP-complet. Cela signifie que si l'on trouve une solution en temps polynomial pour SAT, alors P=NP
SAT∈NP-complet⟹∀L
