> > Par exemple factoriser un nombre est actuellement un problème NP. Si on arrive à factoriser un nombre en temps P, alors tous les problèmes NP pourrons être transformés en P ?
> Oui.
Euh, aux dernières nouvelles, la factorisation en facteurs premiers, c'est NP, mais pas NP-complet. Par exemple, ça se fait en temps polynomial sur un ordinateur quantique, alors qu'il n'y a toujours pas d'algo connus pour résoudre les problèmes NP-complets en temps polynomial sur ordinateurs quantiques (ou alors, j'ai raté un truc).
Résoudre un algo NP-complet en temps polynomial ferait tomber tous les autres, mais factoriser un nombre en facteurs premiers, non, ça ne suffirait pas.
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Matthieu Moy (site web personnel) . En réponse au journal P != NP : la preuve. Évalué à 3.
> Oui.
Euh, aux dernières nouvelles, la factorisation en facteurs premiers, c'est NP, mais pas NP-complet. Par exemple, ça se fait en temps polynomial sur un ordinateur quantique, alors qu'il n'y a toujours pas d'algo connus pour résoudre les problèmes NP-complets en temps polynomial sur ordinateurs quantiques (ou alors, j'ai raté un truc).
Résoudre un algo NP-complet en temps polynomial ferait tomber tous les autres, mais factoriser un nombre en facteurs premiers, non, ça ne suffirait pas.