Discussion :

[Madou41]

Si je suis sure d'avoir trouve une solution p=np pour coloration de graphe
comment proceder a la publication moi qui habite un pays du tiers monde

[dourouc05]

La procédure standard est de rédiger un article scientifique qui présente ton algorithme, une preuve de correction et une autre de complexité au pire cas, puis de le soumettre à un journal (très souvent, c'est gratuit), comme http://toct.acm.org/ ou http://www.springer.com/birkhauser/c...nce/journal/37 (très peu de journaux scientifiques sont édités en français, je n'en connais pas en informatique…). Le processus de publication inclut des phases de relecture, où d'autres personnes vont lire ton article et dénicher les fautes qui s'y trouvent, à toi alors de les corriger.

[Madou41]

Merci pour la repense
Mais comment envoyer ma solution au risque de me faire voler
Aussi ma solution n'a meme pas besoin de calculateur juste une feuille de papier et tres peut de temps

[AdmChiMay]

Une idée parfois utilisée, c'est d'envoyer d'abord ton idée par la poste, sous pli bien scotché, à toi-même ou à une personne de confiance. Ensuite, ne surtout pas l'ouvrir, la date du cachet de la poste "faisant foi" (du moins officiellement en France). La personne de confiance peut aussi être une personne assermentée, comme ton notaire préféré. Là, tu as une date de démarrage.

Ensuite, il y en a aussi qui commencent par une "petite" revue, où moins de gens pointus vont détailler le contenu, et se contenter de publier. Il y en a même qui vont sur des forums internationaux de math pour commencer leur explication et en débattre : la date de publication de tes messages est "mondialement" enregistrée. Mais il faut aussi le vocabulaire et les connaissances pour faire face aux remarques qui vont tomber. Les maths, c'est très rigoureux mine de rien.

En tous cas bonne chance, tu es sur un sujet assez pointu que beaucoup de monde travaille. Il y a déjà un nombre d'exposés assez innombrable, et si ça marche, c'est direct la médaille Fields. Et des millions d'algorithmes qui vont se pencher sur ton cas.

[dourouc05]

Les comités de relecture sont censés soumis à une certaine éthique, il ne devrait y avoir aucun vol (en théorie ; maintenant, j'entends plus parler de rejets de travaux de concurrents qu'autre chose). Sinon, publie d'abord sur arXiv, une plateforme de prépublication, donc sans vérification par un comité extérieur, ce qui limite la possibilité de vol (par exemple, sous https://arxiv.org/list/cs.CC/recent). Reste aussi une plateforme de blog en ligne. Dans tous les cas, tu pourras facilement prouver que tu es à l'origine de l'idée grâce aux dates indiquées (le danger avec la lettre, c'est qu'une fois ouverte elle ne peut plus rien prouver…).

[AdmChiMay]

(le danger avec la lettre, c'est qu'une fois ouverte elle ne peut plus rien prouver…).

Tout à fait. Elle est dans ce cas uniquement utile pour être ouverte par une personne assermentée, le jour où il y a litige (d'où l'idée de l'envoyer à un notaire qui la garde au chaud). Mais c'est vrai que un blog ou un forum suffisent depuis longtemps à poser les dates et la paternité.

Cela fait plus de 30 ans que je vois des épisodes de ce style sur des forums, et actuellement notre cher fanmanga (ou extrazlove ou…) est sur dvp (entre autres) dans une telle démarche .

[Madou41]

Merci pour votre aide
Je crois que je ne vais pas publier ma solution .je vien d'avoir une offre moneable plus interessante que le prix de l'institut clay.

[dourouc05]

Je crois que je ne vais pas publier ma solution .je vien d'avoir une offre moneable plus interessante que le prix de l'institut clay.

Ah oui ? Ou alors tu n'avais tout simplement pas la solution que tu proposais au départ ?

[Madou41]

Pour essayer envoi moi un graph de 50 point et je t'enverrai le nombre minimal de couleur
Pour un pc de grande puissance cela prendrai a peut pres 3,0861586201637e+47 annee a resoudre
Envoi la repense le vendredi matin et tu aura la solution en quelques minutes

[dourouc05]

Cinquante nœuds ? C'est trois fois rien. Je te propose plutôt quelques graphes de mille nœuds : http://mat.gsia.cmu.edu/COLOR/instances.html, https://sites.google.com/site/graphc...ertex-coloring. Combien des instances de cette page peux-tu résoudre (avec les ressources à ta disposition) ? (Mais ce n'est pas parce que tu arrives à résoudre ces instances "rapidement" que tu as forcément un algorithme polynomial…)

Et il faut nettement moins de temps pour résoudre ce problème que ce que prétends. Il n'y a pas que des algorithmes par force brute pour résoudre ce problème. Si tu te contentes d'une solution approchée (donc pas le nombre minimal de couleurs), on a développé de très bonnes heuristiques qui tournent en temps polynomial (par exemple, DSATUR, qui donne une solution optimale avec une probabilité de 90 % : https://fr.wikipedia.org/wiki/DSATUR). Un algorithme générique par programmation dynamique donne des solutions exactes avec moins d'opérations que ton estimation (de l'ordre de 10^20 opérations pour tes 50 nœuds).
Ma source : https://en.wikipedia.org/wiki/Graph_coloring#Algorithms

[Madou41]

Vas pour choisi ton chiffre
Et pour les 50 noeuds c'etait a la main que j'allait les faire. C'est une solution d'imagination en multidimention que j'ai et pas un algorithme que j'ai posé
Mais grace a la betise humaine je vais ecrire le prog qui va avec.

[dourouc05]

Tant que tu as défini une "procédure effective" au sens de Turing, tu as un algorithme : une suite d'opérations que n'importe qui ou n'importe quelle machine pourrait effectuer, simplement en suivant les instructions à la lettre, sans imagination. Sinon, tu es loin d'un P=NP .