probleme np

[invitea121f130]

salut all
je voudrais juste savoir c'est quoi la différence entre un problème np complet et problème np difficile
-----

[GuYem]

Salut ...

[invitea121f130]

What?
tu me cause de cois mecs

[nissart7831]

Salut,

je ne sais pas si ça te suffira, mais tu peux trouver quelques explications dans wikipedia :

http://fr.wikipedia.org/wiki/Th%C3%A...omplexit%C3%A9

Tu as beaucoup d'autres liens sur le web (Google avec NP complet difficile)

[A voir en vidéo sur Futura]

[invite7863222222222]

salut all
je voudrais juste savoir c'est quoi la différence entre un problème np complet et problème np difficile

D'après mes recherches, un problème NP complet est forcement dans NP, mais ce n'est pas nécessaire pour un problème NP difficile qui peut donc être dans une classe de compléxité plus élevée (que NP).

[invitea121f130]

on effet c'est ce que je viens de trouve un probleme np-complet
peux etre soluble par ne machine de turing nom deterministe en un temps polynomiale ce qui est pas le cas du probleme np-difficile

[invite7863222222222]

ce qui est pas le cas du probleme np-difficile

(NP-complet est inclus dans NP-difficile quand même)

[GuYem]

What?
tu me cause de cois mecs

Salut mec, je te cause parce que j'aime bien ta question mais je la comprends pas. J'ai jamais entendu parler des "problèmes NP", tu pourrais expliquer un peu plus en détails histoire de voir si ça peut intéresser des gens.

[invite164710e8]

moi ca m'interesse parce que c un probleme du millenaire

Demontrer que P=NP ou P different de NP
Enfin si tu pouvais nous apporter quelque renseignement ca seré gentil car je comprend l'idée generale mais pas les subtilité
merci d'avance

PS: Qu'est ce qu'une machine de Turing ?==> beaucoup de personne en parle mais sans jamais la definir ...

[nissart7831]

Salut mec, je te cause parce que j'aime bien ta question mais je la comprends pas. J'ai jamais entendu parler des "problèmes NP", tu pourrais expliquer un peu plus en détails histoire de voir si ça peut intéresser des gens.

Salut GuYem,

ça touche à la complexité des algorithmes. Une petite introduction ici.

[invite7863222222222]

Un problème NP (Non déterministe Polynomial et non pas Non Polynomial !) est un problème que l'on sait résoudre en un temps exponentiel.

Un exemple est le fameux problème du voyageur de commerce voulant minimiser la longueur parcourue lors de la visite de N villes.

Aujourd'hui, les mathématiciens ne connaissent qu'une méthode permettant de trouver la solution exacte à ce problème pourtant très simple :

Enumérer bêtement toutes les possibilités , puis choisir celle qui donne la plus petite longueur...

Cette solution est envisageable N très petit, (pour N = 4, on a 4! = 24 possibilités), mais elle ne l'est plus dès que N est légèrement plus élevée.

Par exemple, pour N = 25, il y a déjà 1.5 x 10^25 possibilités.

Le nombre de possibilités augmente en N!, ce qui veut dire que même si la vitesse des ordinateurs augmentent (progression polynomiale), ce n'est pas suffisant pour rattraper la complexité de ces problèmes.

Par exemple, l'algorithme de cryptage RSA est un problème NP, c'est ce qui fait sa réussite.

Un ordinateur actuel devrait passer peut-être 20 ans à énumérer toutes les solutions possibles, pour choisir ensuite celle qui convient.

Même si on avait un ordinateur super puissant pouvant faire le calcul en 2 minutes, il suffirait d'augmenter N de quelques unités pour que l'ordinateur soit à nouveau dépassé et obligé de repasser encore 20 ans à énumérer toutes les solutions.

Voilà pour les problèmes NP.

Les problèmes P, Polynomial, sont ceux dont le temps de calcul de la solution avec le nombre de paramètres n'évolue pas de manière exponentielle, mais polynomiale. Par exemple, un système d'équation linéaire à N variables, est un problème polynomial, P.

En résumé avec un problème NP, sa résolution se fait en x^N et avec un problème P, elle se fait en N^x.

Pendant des années (une trentaine), les plus grands mathématiciens ont essayé de trouver des méthodes efficaces (polynomiales) pour résoudre les problèmes NP mais n'en ont malheureusement jamais trouver.

Il existe des méthodes qui donnent des solutions approchées mais aucune méthode en temps polynomial pour la solution exacte...

Les deux ensembles de problèmes semblent ainsi bien différents, c'est à dire qu'un problème tel que celui du voyageur de commerce ne peut, par définition, pas se résoudre en un temps polynomial.

Les mathématiciens ont donc commencé à essayer de prouver théoriquement qu'un problème NP ne peut pas se résoudre en un temps polynomial, on pensait que ca serait très facile...

Malheureusement, comme vous vous en doutez, on a jamais réussi, impossible de le prouver, on a d'ailleurs jamais réussi à prouver le contraire non plus.

Si bien qu'aujourd'hui, P = NP ? (comprendre l'ensemble des problèmes de classe P est il égal à l'ensemble des problèmes de classe NP ?) est une des 7 énigmes mathématiques encore non résolues du siecle...


NB : personnellement, comme dit dans un autre sujet, je me dit que si on arrive pas à résoudre cette énigme, c'est peut-être que ce problème n'est pas prouvable. D'ailleurs, si vous connaissez des travaux qui vont dans ce sens, ca m'intéresse .

[GuYem]

Ah, merci pour cette réponse détaillée Jreeman, me coucherai moins bète ce soir.

En effet le sujet a l''air intéressant ; on reconnait bien là la folie des mathématiciens qui se disent : "si je n'arrive pas à le résoudre, c'est qu'il ne doit pas y avoir de solutions, alors je vais essayer de montrer qu'il n'y a pas de solutions ...".
Et sur ce coup, pas de bol, on n'arrive même pas à montrer qu'il n'y a pas de solutions

[invite7863222222222]

Oui mais c'est rageant quand même de pas avoir de solution pour un problème aussi simple que celui là.

On arrive à trouver des résultats mathématiques dans d'autres domaines complexes mais on est tout con, devant l'un des plus vieux problèmes du monde...

Ca calme quand même les prétentions des mathématiciens .

[invite6b1e2c2e]

Salut jreeman et autres,

Je ne vois pas pourquoi tu as l'impression que c'est un problème tout con. En plus, je crois me souvenir qu'on a énuméré une liste de problèmes assez différents dont on a réussi à démontrer qu'ils étaient équivalents (au sens où, si on arrive à démontrer qu'un seul est P, alors, les autres le sont aussi).
De plus, on a en aussi pris notre parti dans les problèmes de cryptographie (RSA et compagnie).
Et puis, l'un des plus vieux problèmes du monde, faut peut-être pas poussé ! Les questions d'algorithme ont du être précisément mises en forme vers 1940, et la formulation mathématique P=NP doit dater des années 60, je pense...

__
rvz, que c'est pas parce que c'est dur que c'est indécidable, sinon ç simplifierait beaucoup la progression des maths (Soit un théorème. Preuve : indécidable )

[invite7863222222222]

Quand je dis que le problème est tout con, je veux dire que l'expression du problème est simple et facile à appréhender.

Sinon pour l'indécidabilité, ce n'est qu'un avis personnel et c'est juste une idée que je lancais comme cela au cas où vous sauriez si des travaux ont été fait dans ce sens.

Des problèmes indécidables, il y en a, je crois avoir lu par exemple, qu'on ne peut pas prouver qu'une équation diophantienne n'admet pas de solutions.

Les questions d'algorithme ont du être précisément mises en forme vers 1940, et la formulation mathématique P=NP doit dater des années 60, je pense...

On a formalisé le problème sous la forme P = NP que récemment, mais le problème existe dans la vie pratiques des Hommes depuis plus longtemps que cela.

[invite6b1e2c2e]

Des problèmes indécidables, il y en a, je crois avoir lu par exemple, qu'on ne peut pas prouver qu'une équation diophantienne n'admet pas de solutions.

Bon, on va dire _sauf pour le théorème de Fermat Wiles_
Disons que je suis comme toi, et que je n'en sais rien. Mais bon, selon moi, des problèmes vraiment indécidables, il n'y en a pas tant que ça, mais je t'accorde que c'est quasiment un débat philosophique
Disons qu'il y a des axiomes qui "doivent être moralement vrais", et, disons que tant qu'on n'a pas réduit le problème à un axiome de ce genre, pour moi, il y a tout un travail de preuves "standardes" (Orth ?) à faire.

__
rvz

[invite7863222222222]

D'ailleurs pour les équations diophantiennes, y'a quelque chose qui me chiffonne, on sait prouver qu'une équation diophantienne admet des solutions mais on ne sait pas prouver qu'elle n'en admet pas.

C'est pas contradictoire ?

[invite986312212]

est-ce que tu ne fais pas allusion au dixième problème de Hilbert? si c'est ça je crois que la formulation est plutôt: il n'existe pas d'algorithme universel qui permette de décider si une équation diophantienne admet ou non des solutions.

[invite7863222222222]

est-ce que tu ne fais pas allusion au dixième problème de Hilbert? si c'est ça je crois que la formulation est plutôt: il n'existe pas d'algorithme universel qui permette de décider si une équation diophantienne admet ou non des solutions.

Oui c'est surement ca alors. Je dois y aller. Donc surement @+