Discussion :

[gorgonite]

Vraiment ? C'est intéressant, tu as une URL ?

le document n'est plus accessible... étrange

[Jedai]

Oui, justement, je ne parlais que du théorème : P=NP, sans preuve derrière.
En gros, je disais juste que si on savait seulement que P=NP, ça ne nous avancerait à rien

Effectivement, d'un autre côté, même si on avait seulement la preuve et pas d'algorithme, ça suffirait pour réduire à néant la valeur des algorithmes de cryptage qui s'appuient sur un problème NP-Complet : le fait qu'un tel algorithme existe signifie qu'une agence secrète pourrait l'avoir trouvé, même s'il n'as pas été diffusé.

D'ailleurs, il y a une fausse note dans la phrase, comme P est dans NP, il existe des problèmes dont il existe des solutions en temps polynomial dans P, donc dans NP.

Bien sûr je voulais dire un algo polynomial pour résoudre un problème NP complet.

--
Jedaï

[alex_pi]

Effectivement, d'un autre côté, même si on avait seulement la preuve et pas d'algorithme, ça suffirait pour réduire à néant la valeur des algorithmes de cryptage qui s'appuient sur un problème NP-Complet : le fait qu'un tel algorithme existe signifie qu'une agence secrète pourrait l'avoir trouvé, même s'il n'as pas été diffusé.

Euh, c'est pas si simple hein ! On ne passe pas d'un algorithme indécidable à un algorithme décidable. On passe d'un problème dont la solution est réputée exponentielle à un autre dont la solution est polynomiale. Mais si P = NP, on n'a pas "tous les problèmes se résolve en O(n²)" hein ! Si un algo est trouvé en O(n^32165987), on n'a pas encore résolu tous les problèmes :-)

De plus, je rappelle que la factorisation en nombre premier n'est pas un problème NP complet et qu'il existe un algorithme sous exponentiel (sans être polynomial)