Bien ce que je pensait : tu fait au feeling, comme font tout les programmeurs (même si ils vont dire "y'a pas d'algo adapté à de grande quantitées" au lieu de "np-complet").
C'est difficile de dire qu'il n'y a pas d'algo adapté à de grandes quantités si on ne sait pas ce qu'on cherche. Prenons par exemple les deux problèmes suivants:
- Existe-t-il un chemin passant une fois et une seule par toutes les villes d'une liste donnée ?
- Existe-t-il un chemin passant une fois et une seule par toutes les routes reliant les villes d'une liste donnée ?
Ce sont deux problèmes qui se ressemblent, et quelqu'un qui s'est heurté au premier peut très bien se laisser tenter et conclure que le deuxième est aussi difficile. En réalité, le premier est NP-complet, alors que le deuxième est dans P (et donc probablement pas NP-complet).
Et ensuite un problème np-complet c'est un problème qui a la même complexité que celui qui permet de trouver les clefs privées de GPG à partir des clefs publiques
Je ne suis pas sûr de l'algo utilisé par GPG, mais si tu penses au problème de décomposition d'un nombre en produit de facteurs premiers, on ne sait pas quelle est sa complexité. On pense qu'il est compliqué parce qu'on ne connait pas d'algorithme exact qui soit efficace, mais on n'en est pas sûr.
[^] # Re: Enfin bon
Posté par Yusei (Mastodon) . En réponse au journal Les informaticiens précoces. Évalué à 3.
C'est difficile de dire qu'il n'y a pas d'algo adapté à de grandes quantités si on ne sait pas ce qu'on cherche. Prenons par exemple les deux problèmes suivants:
- Existe-t-il un chemin passant une fois et une seule par toutes les villes d'une liste donnée ?
- Existe-t-il un chemin passant une fois et une seule par toutes les routes reliant les villes d'une liste donnée ?
Ce sont deux problèmes qui se ressemblent, et quelqu'un qui s'est heurté au premier peut très bien se laisser tenter et conclure que le deuxième est aussi difficile. En réalité, le premier est NP-complet, alors que le deuxième est dans P (et donc probablement pas NP-complet).
Je ne suis pas sûr de l'algo utilisé par GPG, mais si tu penses au problème de décomposition d'un nombre en produit de facteurs premiers, on ne sait pas quelle est sa complexité. On pense qu'il est compliqué parce qu'on ne connait pas d'algorithme exact qui soit efficace, mais on n'en est pas sûr.