P = NP, la pire démonstation de l'Histoire ?

[Jeanveux]

Bonjour,



En mathématique et en informatique le problème du voyageur de commerce est un problème d'optmisation combinatoire réputé NP-Complet dont la résolution à partir d'un algorithme en temps polynomiale démontrerai l'égalité de la conjecture mathématique et informatique du problème P=NP.

On démontrera ici l'existence du dit algorithme .

Présentation

Le problème s'énonce donc comme suit dans sa version traditionelle:

1. Etant donné une liste de villes et les distances entre toutes les paires de villes, déterminé le plus court circuit qui passe par chaque ville une et une seule fois ?

Que nous devons démontrer afin de répondre à la question dans sa version décisionelle :

2. Pour une distance D donné, existe-t-il un chemin plus court que D passant par toutes les villes ?


Démonstration:

(version traditionelle)
On peut déterminé que pour un algorithme traitant de toute instance du problème de façon polynomiale, il doit existé pour celui-ci une situation dans le meilleur et le pire des cas.

Pour lequel toute les longueurs ,entre les villes sont de distance équivalente , tout les chemins formant donc une boucle et passant par chaque ville une seul et unique fois et où l'on peut de dire que tout les itinéraires sont les plus court .

Par conséquent nous savons,en généralisant que pour le pire des cas aucun algorithme ne peut résoudre (au sens du calcul et de façon exact) moins rapidement que le meilleur des cas dans une telle situation .

On à donc pour pour cette algorithme le meilleur des cas, où la complexité de l'algorithme équivaut à la complexité de la vérification du résultat,puisqu'il suffit de vérifier dans une telle situation si les conditions sont respectées et qu'on ne peut le faire "qu'en lisant au moins une fois chaque données du problème" (cf:lien youtube de ScienceEtonnante: à partir de 16 minute 35 s),qui lui est P !



Quelque lien qui présenteront le problème du voyageur de commerce et de l'état dans l'art concernant P=NP :

https://www.youtube.com/watch?v=AgtOCNCejQ8

https://en.wikipedia.org/wiki/P_versus_NP_problem


https://en.wikipedia.org/wiki/Travel...lesman_problem

https://fr.wikipedia.org/wiki/Probl%...ur_de_commerce
-----

[Jeanveux]

Hello,

Je reviens pour précisé que cette discussion a avant tout pour moi dans le pires des cas (c'est-à-dire si ce que je dis ci-dessus se révelait faux ou insuffisant) pour but d'évoqué différente piste que j'envisage pour la résolution de P=NP .

Bonne discussion à tous !

[GBZM]

Bonjour,

Ce que tu écris ne fait pas sens. Je pense que tu t'en doutais bien.

[Jeanveux]

Désolé mais j'attend que tu m'explique au moins ce que tu veux dire , cette discussion à pour de me faire évoluer et éventuellement réussir !
Je préviens donc j'apprécierais que toute remarque ce suivent d'explication sur ce qui vous pose problème que se soit dans la compréhension du post initale ou dans l'exposition d'une éventuelle erreur de raisonnement.

Je ne suis pas devin

Merci

[A voir en vidéo sur Futura]

[Liet Kynes]

Pour lequel toute les longueurs ,entre les villes sont de distance équivalente , tout les chemins formant donc une boucle et passant par chaque ville une seul et unique fois et où l'on peut de dire que tout les itinéraires sont les plus court .

4 points équidistants : tu nous fait un dessin ?

[Jeanveux]

Désolé je n'est pas compris ta réponse Liet Kines,tu veux que je fasse un dessins ou tu me demande si je fait un dessein ? Si c'est ce dernier cas non je sais parfaitement qu'un exemple ne suffit pas .

[Liet Kynes]

Si tu veux mettre l'ensemble des points à équidistance les uns des autres sur un plan :

Avec 2 points c'est ok , avec 3 c'est ok mais avec plus de 3 cela semble se compliquer…

[GBZM]

Liet Kynes, ce n'est pas un problème. Le graphe complet peut avoir une fonction de coût sur les arêtes qui est constante (quel que soit le nombre de sommets).

Jeanveux, désolé, j'ai du mal à discuter sur quelque chose qui n'a aucun sens.
Il est sûr que si tous les coûts des arêtes sont les mêmes, il est facile de décider s'il existe un circuit passant une fois et une seule par chaque sommet et revenant au point de départ de coût total plus petit que D. Et alors ?

[gg0]

Bonjour.

II est possible que le français ne soit pas ta langue natale, ce qui expliquerait les fautes de grammaire et d'orthographe; et aussi que la fin de ta longue phrase au début n'a pas de sens.
II faudrait reprendre ton texte pour le rendre lisible. Mais le plus grave c'est que ta "démonstration" n'en est pas une. C'est seulement une suite d'affirmations personnelles qui ne servent à rien. C'est ce que GBZM te disait.
On ne pourra pas t'aider à avancer dans cette preuve, vu que tu n'as rien à apporter (et que personne ne sait faire la preuve).
Désolé !

[MissJenny]

Le problème s'énonce donc comme suit dans sa version traditionelle:

1. Etant donné une liste de villes et les distances entre toutes les paires de villes, déterminé le plus court circuit qui passe par chaque ville une et une seule fois ?

Que nous devons démontrer afin de répondre à la question dans sa version décisionelle :

2. Pour une distance D donné, existe-t-il un chemin plus court que D passant par toutes les villes ?

1) et 2) ne sont pas équivalents. De toutes façons le problème du voyageur de commerce n'est pas un problème d'existence puisque tout est fini.

[GBZM]

Bien sûr que 1) et 2) ne sont pas équivalents, et d'ailleurs jeanveux ne dit pas cela ; inutile donc de lui reprocher !
Le problème décisionnel dérivé du problème du voyageur de commerce est bien un problème d'existence : étant donné D, existe-t-il un circuit hamiltonien de coût total. inférieur à D ? Ce problème décisionnel (à réponse oui ou non) est NP-complet.

[Deedee81]

Salut,

Moi c'est la partie sans démonstration qui me pose problème. Non pas que c'est faux. C'est juste incompréhensible :

On peut déterminé que pour un algorithme traitant de toute instance du problème de façon polynomiale, il doit existé pour celui-ci une situation dans le meilleur et le pire des cas.

Que veux dire "il doit exister une situation dans le meilleur et le pire des cas" : que veux dire (dans ce contexte) "le meilleur et le pire des cas" et de quelle situation parle-t-on ???

Pour lequel toute les longueurs ,entre les villes sont de distance équivalente

C'est quoi des distances équivalentes ????

, tout les chemins formant donc une boucle et passant par chaque ville une seul et unique fois et où l'on peut de dire que tout les itinéraires sont les plus court .

On montre qu'une solution où tous les itinéraires entre villes sont les plus courts n'est PAS toujours la trajectoire (globale) la plus courte. MAIS tu n'as pas prouvé que l'algorithme polynomial conduit à ça (au contraire, il pourrait y conduire uniquement dans les cas où les liens les plus courts fonctionnent !!!! Il faudrait le prouver ou le réfuter).

Tu dis "on peut déterminer". Mais une démonstration ne commence jamais par "on peut déterminer". On ne dit pas on peut : on le fait

Un conseil Jeanveux : écrit ta ou tes démonstrations de manière formelle, mathématique (surtout en mathématique du supérieur), sans utiliser un seul mot de français. Ici pour une démonstration aussi courte c'est facile. Ainsi, toi (et les autres) tu verras tout de suite si c'est correct ou pas.

Sinon pour répondre au titre : non, j'ai connu pire : une démonstration du grand théorème de Fermat utilisant le fait que l'espace est à trois dimensions : véridique

[Jeanveux]

Rebonjour ,

Je vais quand même tenter de clarifié mon raisonnement :


Si on admet que P est différent de NP, alors par construction,pour l'ensemble des problèmes NP il n'existe aucune instance qui peut être résolu de manière polynomiale .
Or en prenant un problème NP-Complet et en trouvant une seule instance pour ce problème,on peut alors montrer que l'ensemble des problèmes NP possède au moins une instance résoluble de cette manière.
Ici on prend le problème du voyageur de commerce , on prouve qu'il est possible de constuire une instance de n'importe quel taille qui est toujours résoluble de manière polynomiale si :

tout les coûts des arrêtes sont les mêmes (comme la compris GBZM)

A partir de la j'ai voulu montrer que le degré du polynôme est équivalent à celui de l'algorithme qui nous permet de vérifier si le circuit respecte toute les conditions du problème

Il suffit enfin de vérifié si le coût de ce circuit est bien inférieur à longeur D donner pour résoudre le problème dans sa version décisionelle .

Voilà le raisonnent initiale en espérent m'être mieux exprimé

Merci pour vos réponses !

[gg0]

Bonjour.

Ton raisonnement pêche à la base : personne ne met en doute qu'il existe des situations particulières pour lesquelles un algorithme polynomial, voire linéaire, suffit. C'est un algorithme généraliste qui est demandé.
De ce fait, ton raisonnement élémentaire ne sert à rien.

Tu devrais te renseigner un peu plus sérieusement avant de présenter tes idées, tu passes pour un petit rigolo...

Cordialement.

[Jeanveux]

Tu n'as pas compris ce que j'ai voulu dire,je sais déjà pour l'algorithme généraliste , ce que je veut dire c 'est justement si P était véritablement différent de NP, alors quelque soit l'instance du problème on ne devrait jamais trouver d'algorithme polynomiale même dans des cas simple ,puisque par définition il ne serait plus alors strictement NP .

Par définition si P était différent de NP, toutles cas du problème serait NP et donc non résolvable en temps polynomiale.

[gg0]

J'ai très bien compris ce que tu disais et que tu répètes, et c'est une incompréhension de ta part. Ce que tu dis est faux.

Inutile d'insister, tu ne parles même pas de P=NP, tu ne connais pas le sujet.

NB : de nombreux mathématiciens de haute volée ont étudié la question sans la résoudre, mais tu viens avec un raisonnement élémentaire en croyant faire mieux qu'eux ! Reviens sur Terre !

[Médiat]

si P était véritablement différent de NP, alors quelque soit l'instance du problème on ne devrait jamais trouver d'algorithme polynomiale même dans des cas simple

Difficile de faire plus faux sur le sujet, il est extrêmement simple de trouver des instances de tous les problèmes NP qui se résolvent en temps polynomial (voire même linéaire), je vous laisse trouver un exemple pour le voyageur de commerce (c'est trivial)

[GBZM]

Lis mieux le fil, Mediat, et tu verras que justement jeanveux a bien trouvé une instance du problème décisionnel du voyageur de commerce où l'algorithme de réponse n'est même pas linéaire en le nombre de sommets : quand tous les coûts des arêtes sont égaux, il suffit de multiplier le coût commun par le nombre de sommets pour savoir s'il existe un circuit hamiltonien de coût total plus petit qu'un D fixé à l'avance.
Le problème de jeanveux, c'est qu'il pense que cela montre P=NP. C'est une incompréhension complète de ce qu'est que la classe de complexité d'un problème. On a beau lui expliquer qu'il doit revoir la définition de la classe P, il refuse de comprendre.

[Médiat]

Ah ouais, c'est encore pire que ce que je pensais

[albanxiii]

J'ai fait du ménage dans cette discussion, avec mes excuses pour les messages de celleux qui ont fini comme dommages collatéraux.

[Deedee81]

Salut,

Tu n'as pas compris ce que j'ai voulu dire,je sais déjà pour l'algorithme généraliste , ce que je veut dire c 'est justement si P était véritablement différent de NP, alors quelque soit l'instance du problème on ne devrait jamais trouver d'algorithme polynomiale même dans des cas simple ,puisque par définition il ne serait plus alors strictement NP .

Donc pour toi les ensembles {1,2} et [1,2,3} ne sont pas différents sinon "on ne devrait jamais trouver d'éléments en commun".

Non, mais ça t'arrive de réfléchir ? Personne n'a jamais dit que dans le classe NP tous les problèmes étaient insolubles par un algorithme polynomial. Cette idée absurde est une pure invention de ta part. D'ailleurs il existe nombre d'algorithmes polynomiaux utilisés en pratique pour des problèmes NP qui sont largement utilisés car les problèmes rencontrés ont le bon goût de ne pas être trop lourds. On en rencontre notamment en théorie des circuits (réseaux électriques, conception de cartes électroniques, etc...). Et j'en avais moi-même conçu un pour un problème complexe de panification. D'ailleurs la définition de NP dit que P est inclut à NP. Un strict minimum de recherche te l'aurait montré et t'aurait éviter lâcher une telle énormité (qui a dû en faire rire plus d'un).

Je constate donc que :
1) Tu n'as fait aucune recherche sérieuse sur P et NP avant de réfléchir au problème
2) Tu n'as pas suivi mon conseil de formalisation qui t'aurait éviter un message aussi absurde, tu as préférer continuer dans les affirmations floues ou absurdes

J'en déduis donc que tu ne veux pas vraiment faire de mathématiques. Juste faire ton intéressant. Peut-être involontairement, mais le fait est là.