Methode problèmes NP complets

Discussion générale entre passionnés et amateurs de mathématiques sur des sujets mathématiques variés
Robot

par Robot » 25 Sep 2015, 19:11

Doraki a écrit:J'croyais qu'on savait seulement qu'il était NP-difficile ?
C'est facile de vérifier qu'un parcours donné à une longueur donnée, mais c'est beaucoup plus dur de montrer que c'est vraiment le parcours le plus court.


Tu as raison, je n'ai pas été assez précis : c'est le problème de décision associé au problème d'optimisation qui est NP-complet : étant donné D, existe-t-il un chemin visitant toutes les villes de longueur totale plus petite que D ? Là, la vérification d'une solution est clairement dans P.



Sylviel
Modérateur
Messages: 6466
Enregistré le: 20 Jan 2010, 14:00

par Sylviel » 25 Sep 2015, 19:12

ça n'a pas de sens de dire qu'un "axiome est démontré".
Un axiome c'est une règle de base que tu prends pour pouvoir montrer le reste. Typiquement tu as besoin d'axiome pour pouvoir faire un "raisonnement logique", car les règles de la logique sont issus des axiomes...

Par exemple le fait de pouvoir choisir un élément dans un ensemble est un axiome (et en plus un axiome qui n'est pas toujours accepté).

Ce qui est montré c'est qu'avec tels axiomes ont peut obtenir tel chose. Ou encore que tel ensemble d'axiome est équivalent à tel autre (comprendre à partir de l'un je peut montrer l'autre et réciproquement).
Merci de répondre aux questions posées, ce sont des indications pour vous aider à résoudre vos exercices.

lulu math discovering
Membre Rationnel
Messages: 631
Enregistré le: 24 Aoû 2015, 11:47

par lulu math discovering » 25 Sep 2015, 19:17

Les mathématiques ont leurs axiomes et la logique a les siens non ?
Ce qui expliquerait ce que je te dis.

De même la physique, qui s'appuie sur les maths, a ses axiomes qui pourraient éventuellement être démontrés mathématiquement (pourquoi pas ?).

Après je suis loin d'être incollable sur le sujet et je n'arrive pas à retrouver ma source, il est donc tout à fait possible que je raconte de grosses bêtises.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 25 Sep 2015, 19:42

Robot a écrit:Tu as raison, je n'ai pas été assez précis : c'est le problème de décision associé au problème d'optimisation qui est NP-complet : étant donné D, existe-t-il un chemin visitant toutes les villes de longueur totale plus petite que D ? Là, la vérification d'une solution est clairement dans P.

Et si la solution d`un probleme "repute" NP (sans entrer dans les details des NP) pouvait etre resolu en temps polynomial?
Qu`en serait-il de ces mathematiciens qui declarent que tel probleme est NP et tel autre P?
Ou est-ce qu`ils se cacheraient donc?

Ce qui m`agace le plus c`est cette tendance a hierarchiser les problemes.
Pour un enfant "normal" de 3 ans qu`est-ce qu`un probleme NP ou P?
Un comateux n`en a rien a cirer de tous ces problemes.
Tout ce qui est developpe au niveau intellectuel et abstrait exclu les 2/3 de l`humanite.
Ah! les philosophes aussi! Qu`est-ce le mec qui cherche a assouvir sa soif en plein desert en a a cirer avec la philosophie. Ce qui me tue c`est quand des gens, relax dans leur confort, "pensent" pour tous les autres. Ca c`est bon, ca ce n`est pas bon, ca c`est Halal ou Cacher et ca ce ne l`est pas. Je ne parle pas des politiciens et des religieux.
Quand les "mathematiciens" sont incapables de solutionner les problemes reels, ils se refugient dans l`abstraction aux relents d`arts.
Quand j`ouvre une revue mathematiques dites de "tres haut niveau" et que je m`amuse a lire un article, je me dis mais bordel de merde " a qui parle ce monsieur?". Bien sur, il parle a ses condisciples. Que leur raconte-t-il? Que cela et cela implique cela et que de cela on peut arriver et au bout du labyrinthe et des dedales de l`abstraction hourrah! le resultat! Oui, et apres? Sais-tu factoriser un tres grand nombre semi-premier? Un non categorique et honteux! rien d`autre. Alors a quoi cela te sert-il de connaitre tout cela. Medaille Fields, Medaille Fields, budget, argent, gloire, etc... voila ce qui fait bouger cette bande de bandits!

Robot

par Robot » 25 Sep 2015, 19:45

Non, "démontrer des axiomes" n'a pas de sens.
La logique mathématique fait partie des mathématiques, et donc l'assertion "Les mathématiques ont leurs axiomes et la logique a les siens" est dénuée de fondement.
Je ne vois pas non plus ce que tu veux dire par "démontrer les axiomes de la physique".
Ton discours reste dans le flou, sans aucun élément précis qu'on pourrait discuter.

lulu math discovering
Membre Rationnel
Messages: 631
Enregistré le: 24 Aoû 2015, 11:47

par lulu math discovering » 25 Sep 2015, 19:46

Tu es ici pour rager ou quoi ?

lulu math discovering
Membre Rationnel
Messages: 631
Enregistré le: 24 Aoû 2015, 11:47

par lulu math discovering » 25 Sep 2015, 19:56

C'est que j'ai appris ça il y a longtemps et je n'arrive pas à retrouver d'informations sur le sujet.

J'ai un ami tout particulièrement passionné de logique (vous savez le genre quand il dit quelque chose sur le sujet, il vérifie deux fois que c'est vrai) qui m'a appris ça.

Sinon, concernant les "axiomes de tel ou tel domaine", ben il me semble que la physique possède ses propres suppositions de base qui permettent, comme en maths, de construire un raisonnement.

On peut démontrer des phénomènes physiques (ou plutôt les prévoir) grâce aux maths, et idem pour les maths avec la logique (une démonstration mathématiques n'est pas un raisonnement complet de logique), pourquoi ne pas poursuivre jusqu'aux axiomes ?

En physique, on ne démontre pas une relation mathématique, on l'exploite.
En maths, on ne démontre pas que le raisonnement par récurrence est valide, on l'utilise.

J'espère que tu as compris le fond de ma pensée.

Robot

par Robot » 25 Sep 2015, 19:58

Mario2015 a écrit:Et si la solution d`un probleme "repute" NP (sans entrer dans les details des NP) pouvait etre resolu en temps polynomial?
Qu`en serait-il de ces mathematiciens qui declarent que tel probleme est NP et tel autre P?
Ou est-ce qu`ils se cacheraient donc?


Tu ne comprends vraiment rien à rien. Les mathématiciens ne "déclarent" pas, ils prouvent. Un certain nombre de problèmes ont été prouvés NP-complets. Si un jour quelqu'un prouve qu'un de ces problèmes est dans la classe P, alors il aura prouvé P=NP (et gagné le million de dollars de l'Institut Clay). Qu'attends-tu pour le faire, toi qui te coltines aux problèmes réels que ne savent pas aborder les mathématiciens ?

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 25 Sep 2015, 20:09

Mario2015 a écrit:Et si la solution d`un probleme "repute" NP (sans entrer dans les details des NP) pouvait etre resolu en temps polynomial?

ce serait un résultat surprenant et tu aurais peut-être 1000000$ selon le problème en question.
Qu`en serait-il de ces mathematiciens qui declarent que tel probleme est NP et tel autre P?

Personne n'a dit qu'un problème NP ne pouvait pas être dans P, je ne vois pas pourquoi tu t'insurges. (encore une fois, 1000000$ si tu montres qu'un problème NP n'est pas dans P)
Pour un enfant "normal" de 3 ans qu`est-ce qu`un probleme NP ou P?
Un comateux n`en a rien a cirer de tous ces problemes.
Tout ce qui est developpe au niveau intellectuel et abstrait exclu les 2/3 de l`humanite.

on est pas sur un forum pour les gamins de 3 ans, et à mon avis ce n'est pas la seule chose qui exclue les 2/3 de l'humanité.
Sais-tu factoriser un tres grand nombre semi-premier? Un non categorique et honteux! rien d`autre. Alors a quoi cela te sert-il de connaitre tout cela.

Qu'est-ce que ça a de honteux ??? Si tu prétends pouvoir le faire avec tes algos maison que tu gardes jalousement secrets, je t'invite à aller rafler tous les prix RSA.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 25 Sep 2015, 20:22

Robot a écrit:Tu ne comprends vraiment rien à rien. Les mathématiciens ne "déclarent" pas, ils prouvent. Un certain nombre de problèmes ont été prouvés NP-complets. Si un jour quelqu'un prouve qu'un de ces problèmes est dans la classe P, alors il aura prouvé P=NP (et gagné le million de dollars de l'Institut Clay). Qu'attends-tu pour le faire, toit qui te coltines aux problèmes réels que ne savent pas aborder les mathématiciens ?

Ils croient avoir prouve jusqu`a ce qu`un "intrus" (un inconnu de la communaute mathematique) prouve le contraire.
Tout le probleme reside dans une chose essentielle : l`approche.
Qui dit approche dit imagination creative.
On utilise des massues pour ecraser un moustique.
Une fois sur un forum mathematiques, j`ai pose un probleme. Deux types d`un certain niveau (niveau experts du forum les mathematiques.net) me disent : Pas possible de le solutionner et ils me sortent leur charabia de complexite avec des tailles galactiques. En 2 minutes, je leur donne la solution que j`avais. Reaction? Silence total et disparition de ce forum. Je me suis bien marre!
Autres hypotheses : imagine que quelqu`un puisse factoriser 2 tres grands nombres semi-premiers sur 10 en temps polynomial. Ou serait classe le probleme de la factorisation?
Idem pour le probleme du voyageur de commerce. En temps polynomial il donne avec exactitude la longueur du chemin le plus court. Ou serait classe ce probleme?

La discussion entre moi, ignorant presume (c`est Robot qui le dit) et le pseudo Robot est la pour y rester j`espere. Je fais confiance aux archivistes.
Le jour viendra ou je pisserai de rire.
Je n`ai jamais reconnu aucune autorite quand il s`agit de la pensee sous toutes ses formes. Aucune. Les bipedes sont les memes tout est question du stupide environnement dans lequel ils grandissent.
Robot n`est ni plus ni moins intelligent que n`importe quel bipede sur terre. Il a eu plus de chance qu`un autre d`avoir acces a une certaine abstraction.
Dans quelques siecles les gamins du primaire se gausseront d`Euler, Villani, Avila, Ramanujan, Terence Tao ou autres.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 25 Sep 2015, 20:29

C`est quand meme terrible de voir les gens raisonner en termes d`argent.
Si c`est cela qui vous motive, alors vous ne faites que confirmer ce que j`ai dit plus haut.
Vaut mieux changer de sujet a mon avis et repondre au monsieur qui a poste un pdf.

lulu math discovering
Membre Rationnel
Messages: 631
Enregistré le: 24 Aoû 2015, 11:47

par lulu math discovering » 25 Sep 2015, 20:56

Tu ne comprends vraiment rien à rien. Les mathématiciens ne "déclarent" pas, ils prouvent. Un certain nombre de problèmes ont été prouvés NP-complets. Si un jour quelqu'un prouve qu'un de ces problèmes est dans la classe P, alors il aura prouvé P=NP (et gagné le million de dollars de l'Institut Clay). Qu'attends-tu pour le faire, toit qui te coltines aux problèmes réels que ne savent pas aborder les mathématiciens ?

Ils croient avoir prouve jusqu`a ce qu`un "intrus" (un inconu de la communaute mathematique) prouve le contraire


Je ne m'y connais pas beaucoup, mais prouver qu'un problème est NP ne contredit aucunement le fait que NP=P.

Doraki
Habitué(e)
Messages: 5021
Enregistré le: 20 Aoû 2008, 13:07

par Doraki » 25 Sep 2015, 21:15

LOL le pdf est à mourir de rire.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 25 Sep 2015, 21:42

Doraki a écrit:LOL le pdf est à mourir de rire.

On ne rit pas de quelqu`un qui fait un effort sauf s`il recopie le travail d`un autre.
On lit tout simplement on s`efforce d`aller jusqu`au bout et apres on se forge un jugement.
S`il y a de la matiere interessante a extraire en oubliant l`aspect forme on engage la discussion.
Autrement, on passe son chemin.
La personne qui a ecrit ce pdf n`a pas du tout creuse la question ne serait-ce que de maniere superficielle. Un matheux niveau lycee qui fait le tour d`internet sur la question peut surement faire mieux.
Bonne chance a lui!
Ps : je ne ris jamais des gens qui travaillent mais je ris tres souvent des gens qui sont gaves de certitudes et qui ont l`esprit formate par leur environnement.
La pensee devrait etre libre : ni gourou ni maitre.

Robot

par Robot » 26 Sep 2015, 00:35

Mario2015, impossible d'avoir une discussion scientifique qui tienne debout avec toi. Tu sembles avoir un sérieux problème avec les maths, mais ce n'est pas mon boulot de le soigner.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 26 Sep 2015, 01:21

Robot a écrit:Mario2015, impossible d'avoir une discussion scientifique qui tienne debout avec toi. Tu sembles avoir un sérieux problème avec les maths, mais ce n'est pas mon boulot de le soigner.

A vrai dire, je n`ai aucun probleme avec les maths.
C`est une discipline ou je brillais adolescent : 1er du lycee (j`etais en terminale). Jamais eu moins que 20/20. J`ai decouvert le calcul integral par moi-meme.
Mon gros probleme en revanche c`est avec les mathematiciens pas tous heureusement.
La majorite des mathematicens ou du moins de ceux qui se proclament comme tels sont juste des gens qui ont potasse leurs cours, appris (je dis bien appris) des centaines d`exercices et de definitions. Ceux-la, je les deteste. J`en ai connu quelques-uns quand j`etais au lycee. Ils sont devenus mathematiciens par la force du travail. Mais ils n`ont en aucun cette force profonde qui vous pousse vers la solution de maniere quasi instinctive voire "animale".
Malheureusement, a cause de problemes sociaux plus urgents et de probleme de sante, j`ai du abandonner mon reve : devenir chercheur en mathematiques, alors que tous mes profs de maths ne voyaient que cela. J`etais fait pour les maths.
La, j`ai cesse de travailler il y a plus de 30 ans.
J`ai repris mais sans but precis car je ne suis ni a la recherche de gloire, ni en quete d`argent. Je vis decemment et cela me suffit.
Si je me balade dans Internet c`est plus pour occuper mon cerveau qu`autre chose.
Et quand tu me parles de "soigner" etc..., je comprends tout de suite ton genre et je visualise le personnage..

alphamethyste
Membre Relatif
Messages: 290
Enregistré le: 01 Mai 2015, 08:06

par alphamethyste » 26 Sep 2015, 16:27

Mario2015 a écrit:
J`ai repris mais sans but precis car je ne suis ni a la recherche de gloire, ni en quete d`argent. Je vis decemment et cela me suffit.

car ? :triste:
Je ne connais aucun mathématicien* (même ceux qui ont reçus des prix) et dont le but était de laisser un nom à la postérité ou de se faire du fric ou dont les travaux était dirigés afin de gagner un prix
Ils ont tous en commun d'avoir un but précis mais non basé sur des considérations sociales (ou financières)
Il existe des gens qui vivent misérablement dans le parfait inconito et qui aiment les maths : leur but est d'arriver à faire ce qu'ils ont décidés de faire, c'est ainsi qu'en mourant ils ont réussit leur vie
De plus un mathématicien est mathématicien jusqu'à la tombe et non pas jusqu'au jour où il a obtenu un prix

*si tu connais un contre exemple dit-le, mais prouve qu'il soit mort en mathématicien et non dans un autre domaine (donc inutile de me citer quelqu'un encore vivant: va falloir attendre qu'il meure et des fois ça peut prendre longtemps , surtout s'il est jeune)

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 26 Sep 2015, 18:03

alphamethyste a écrit:car ? :triste:
Je ne connais aucun mathématicien* (même ceux qui ont reçus des prix) et dont le but était de laisser un nom à la postérité ou de se faire du fric ou dont les travaux était dirigés afin de gagner un prix
Ils ont tous en commun d'avoir un but précis mais non basé sur des considérations sociales (ou financières)
Il existe des gens qui vivent misérablement dans le parfait inconito et qui aiment les maths : leur but est d'arriver à faire ce qu'ils ont décidés de faire, c'est ainsi qu'en mourant ils ont réussit leur vie
De plus un mathématicien est mathématicien jusqu'à la tombe et non pas jusqu'au jour où il a obtenu un prix

*si tu connais un contre exemple dit-le, mais prouve qu'il soit mort en mathématicien et non dans un autre domaine (donc inutile de me citer quelqu'un encore vivant: va falloir attendre qu'il meure et des fois ça peut prendre longtemps , surtout s'il est jeune)


Sais-tu que l`arithmetique etait il y a quelques decennies le "parent" pauvre des mathematiques. Or depuis que l`on a decouvert l`interet des nombres premiers en cryptologie ce fut la ruee vers l`or.
Nous vivons dans une societe ou l`argent est le Dieu adule de quasiment tout le monde. J`imagine deja les politiciens crier qu`ils ne cherchent pas a s`enrichir mais a servir l`interet general et surement que j`eclate de rire.
Ici meme et ailleurs d`ailleurs les intervenants mathematiciens de quelque niveau ne repondent pas aux questions en PREMIER mais leur souci c`est leur ego. Quoi? Un petit minus inconnu dit avoir resolu tel ou tel probleme??? Et comme predit l`ironie, le mepris, voire le rapetissement deviennent strategie de reponse.
Les mathematiques avant d`etre une technique c`est avant tout des idees. Sans nouvelles idees les mathematiques seraient reduits a de la "cuisine" : c`est quoi le probleme? c`est relie a la theorie des graphes bon alors appliquons tel ou tel algorithme etc.. Du couscous que vous voulez alors ouvrons notre livre de recettes. Couscous royal? couscous merguez? couscous senegalais? etc....
On cree des automates, des pavloviens malheureusement qui donnent des reponses parfois meme sans savoir ce qu`il y a derriere.
Je prefere de loin pour un probleme connu voire avec solution connue une NOUVELLE approche completement originale. Cela ouvre des pistes nouvelles.

beagle
Habitué(e)
Messages: 8707
Enregistré le: 08 Sep 2009, 16:14

par beagle » 26 Sep 2015, 18:07

"démontrer des axiomes n'a pas de sens"
oui et non,
car c'est un peu jouer sur les mots.
Voici tiré des éléments d'Euclide de wikipedia:
"Des cinq postulats énoncés dans le livre I, le dernier, dont on déduit le postulat des parallèles : « en un point extérieur à une droite, ne passe qu'une unique droite qui lui est parallèle », a toujours semblé moins évident que les autres. Plusieurs mathématiciens soupçonnèrent qu'il pouvait être démontré à partir des autres postulats, mais toutes les tentatives pour ce faire échouèrent. Vers le milieu du XIXe siècle, il fut démontré qu'une telle démonstration n'existe pas, que le cinquième postulat est indépendant des quatre autres et qu'il est possible de construire des géométries non euclidiennes cohérentes en prenant sa négation."

cela parle bien de démonstration, donc parler de démonstration d'axiome n'est pas dénué de sens.
Maintenant on retombe sur les précisions de Sylviel:
"Ce qui est montré c'est qu'avec tels axiomes ont peut obtenir tel chose. Ou encore que tel ensemble d'axiome est équivalent à tel autre (comprendre à partir de l'un je peut montrer l'autre et réciproquement)."

Il y a certes une nuance, mais cela parle bien de démonstration d'axiomes...
Certainement ça que lulu avait entendu j'imagine...
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.

Mario2015
Membre Relatif
Messages: 306
Enregistré le: 04 Jan 2015, 15:46

par Mario2015 » 26 Sep 2015, 18:40

Tres serieusement en quoi cela avance la resolution d`un probleme qu`un axiome soit demontrable ou pas, demontre ou pas?
En rien! C`est une perte de temps.
Idem pour leur theorie de la complexite.
Savoir qu`un probleme est difficile ou pas ne le solutionne pas!

 

Retourner vers ⚜ Salon Mathématique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 15 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite