Discussion:Fonction à sens unique
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par les projets Cryptologie et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| B | Élevée |  | Cryptologie (discussion • critères • liste • stats • hist. • comité • stats vues) |
| Faible |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Le problème du sac à dos est NP-complet, c'est-à-dire ... modifier
Je n'aurais pas écrit la phrase « le problème du sac à dos est NP-complet, c'est-à-dire qu'il n'existe presque certainement aucun algorithme capable de calculer une solution en un temps qui croisse comme un polynôme en n » pour les raisons suivantes:
- L'affirmation qu'il n'existe pas, d'algorithmes polynomiales est majoritaire certes, mais pas partagée par tout le monde. On ne peut pas donc la mettre dans un encyclopédie. Sur la véracité de cette affirmation, je suis agnostique.
- « Presque certainement »: les probabilités n'ont rien à voir ici.
--Pierre de Lyon (discuter) 26 novembre 2015 à 09:04 (CET)
- En effet c'est maladroit... --Roll-Morton (discuter) 26 novembre 2015 à 09:25 (CET)
Qu'est-ce que la fonction L ? modifier
Je ne sais pas ce qu'est la fonction L qui est utilisée pour donner la complexité de la factorisation d'un entier. Est-ce liée à l'article Fonction L qui définit plusieurs fonctions sous ce nom et/ou à la série L de Dirichlet ? Pierre Lescanne (discuter) 19 octobre 2022 à 09:23 (CEST)
- Bonjour,
- Il s’agit de la notation L utilisée pour quantifier « de manière lisible » (d'après les théoriciens des nombres) les complexités sous-exponentielle mais superpolynomiales. Je suis d'accord, il faudrait le spécifier quelque part. Fabrice Mouhartem (discuter) 14 mars 2023 à 15:14 (CET)