un probleme NP-complet ne peut pas etre résolu en un temps polynomiale sur une machine de turing deterministe ...
Donc tu viens de dire que NP-complet est différent de P (cad qu'on ne pourras jamais trouver d'algo polynomial pour un pobleme NP-complet) , donc tu viens de gagner un prix Clay.
L'une des seule chose qu'on sait des NP-complet c'est qu'ils sont résolus en un temps polynomial sur une machine non déterministe.
De la a dire que ca implique qu'on ne peux pas le faire sur une machine déterministe, c'est un pas que je ne franchirais pas.
(un algo O(1) sur une machine déterministre donnera sans doute un algo O(1) sur une non déterministe, et O(1) c'est polynomial (de degré 0 ))
[^] # Re: d'un autre coté ...
Posté par briaeros007 . En réponse au journal La NSA et la vie privée. Évalué à 3.
Donc tu viens de dire que NP-complet est différent de P (cad qu'on ne pourras jamais trouver d'algo polynomial pour un pobleme NP-complet) , donc tu viens de gagner un prix Clay.
L'une des seule chose qu'on sait des NP-complet c'est qu'ils sont résolus en un temps polynomial sur une machine non déterministe.
De la a dire que ca implique qu'on ne peux pas le faire sur une machine déterministe, c'est un pas que je ne franchirais pas.
(un algo O(1) sur une machine déterministre donnera sans doute un algo O(1) sur une non déterministe, et O(1) c'est polynomial (de degré 0 ))