NP (complexité)La classe NP est une classe très importante de la théorie de la complexité. L'abréviation NP signifie « non déterministe polynomial » (« en »). Un problème de décision est dans NP s'il est décidé par une machine de Turing non déterministe en temps polynomial par rapport à la taille de l'entrée. Intuitivement, cela revient à dire qu'on peut vérifier « rapidement » (complexité polynomiale) si une solution candidate est bien solution.
Logarithme intégralEn mathématiques, le logarithme intégral li est une fonction spéciale définie en tout nombre réel strictement positif x ≠ 1 par l'intégrale : où ln désigne le logarithme népérien. La fonction n'est pas définie en t = 1, et l'intégrale pour x > 1 doit être interprétée comme la valeur principale de Cauchy : Quand x tend vers +∞, on a l'équivalence c'est-à-dire que D'après le théorème des nombres premiers, la fonction de compte des nombres premiers π(x) est équivalente à x/ln(x), donc à li(x), qui en fournit par ailleurs une meilleure approximation.
