lambda calcul !

Citation:

---

Envoyé par Jedai

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

---

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

Citation:

---

Envoyé par millie

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é.

Citation:

---

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ï

Citation:

---

Envoyé par Jedai

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)