On ne parle pas de la même chose : je persiste et je signe en disant que trouver un facteur d'un nombre n se fait en sqrt(n), donc la difficulté augmente en racine de n avec n. C'est exponentiel, mais en puissance 1/2...
Ce que dit le texte en référence, c'est que la difficulté augmente exponentiellement (avec une puissance > 1) en fonction DU NOMBRE DE CHIFFRES NECESSAIRES pour décrire n :
Pour n = 100, 3 chiffres seulement sont nécessaires.
Si tu décris le problème en étudiant l'exposant dans une base donnée, tu passes d'un problème de taille n en exp(n).
Au fait, j'ai beau relire le texte, je n'arrive pas à trouver où ils prétendent que c'est NP-difficile. Ce qu'il faut comprendre, c'est qu'il est facile actuellement d'augmenter le nombre de chiffres pour décrire un nombre : on multiplie par 1000 le nombre (de 3 l'exposant en base 10), on augmente de facto le temps de calcul par 30... Ce qui finit vite pas devenir gros.
Pour finir, j'ai un DEA d'info et j'ai suivi des cours de complexité algorithmique et je bosse actuellement sur des problème NP-difficiles si pas plus. Ce qui ne m'empêche pas de dire des bétises :)
[^] # Re: Un nouvel algo de compression ?
Posté par Olivier Dupuis . En réponse à la dépêche Un nombre premier exécutable ... illégal ?. Évalué à -1.
Ce que dit le texte en référence, c'est que la difficulté augmente exponentiellement (avec une puissance > 1) en fonction DU NOMBRE DE CHIFFRES NECESSAIRES pour décrire n :
Pour n = 100, 3 chiffres seulement sont nécessaires.
Si tu décris le problème en étudiant l'exposant dans une base donnée, tu passes d'un problème de taille n en exp(n).
Au fait, j'ai beau relire le texte, je n'arrive pas à trouver où ils prétendent que c'est NP-difficile. Ce qu'il faut comprendre, c'est qu'il est facile actuellement d'augmenter le nombre de chiffres pour décrire un nombre : on multiplie par 1000 le nombre (de 3 l'exposant en base 10), on augmente de facto le temps de calcul par 30... Ce qui finit vite pas devenir gros.
Pour finir, j'ai un DEA d'info et j'ai suivi des cours de complexité algorithmique et je bosse actuellement sur des problème NP-difficiles si pas plus. Ce qui ne m'empêche pas de dire des bétises :)