Et le fait que P!=NP ne change rien du tout non plus puisque cela ne prouve pas que nos algo actuels ne peuvent pas être réduits. Ca prouve juste qu'il existe au moins un algo qui ne puisse pas.
Euh non... ça va bien plus loin: pour tous les problèmes NP-complets (et il y en a un paquet de connus), on saura alors qu'il sera impossible de trouver un algorithme polynomial déterministe.
Cela dit, dans la pratique... ça ne prouve pas, par exemple, que l'ensemble des instances d'un problème générées, disons, pour rester dans le cas crypto, par un générateur de clés donné va donner une sous-classe de problèmes NP-complète.
Donc bref, de toute façon, ça ne veut pas dire que le boulot s'arrête là !
[^] # Re: Il dit qu'il est pas d'accord.
Posté par Aldoo . En réponse au journal P != NP : la preuve. Évalué à 2.
Euh non... ça va bien plus loin: pour tous les problèmes NP-complets (et il y en a un paquet de connus), on saura alors qu'il sera impossible de trouver un algorithme polynomial déterministe.
Cela dit, dans la pratique... ça ne prouve pas, par exemple, que l'ensemble des instances d'un problème générées, disons, pour rester dans le cas crypto, par un générateur de clés donné va donner une sous-classe de problèmes NP-complète.
Donc bref, de toute façon, ça ne veut pas dire que le boulot s'arrête là !