Fonction négligeable (informatique)

Une fonction négligeable en informatique fondamentale, surtout en cryptographie et en complexité algorithmique, est une notion qui permet de caractériser (souvent pour en ignorer les effets) une fonction mathématique dont la contribution est faible par rapport à une référence. Il s'agit d'une notion asymptotique, qui ne prend son sens que lorsqu'on s'intéresse au comportement des fonctions sur de très grandes entrées. Enfin, une fonction n'est négligeable que vis-à-vis d'une classe de complexité donnée ; dans l'extrême majorité des cas, la classe implicitement considérée est polynomiale. Une fonction est négligeable si elle décroît plus rapidement que l'inverse de tout polynôme. Mathématiquement, est dite négligeable si pour tout n à partir d'un certain rang où représente la domination asymptotique en notation de Landau. Définie ainsi, la notion est relative à la classe de problèmes résolubles en temps polynomial, puisque représente toute fonction négligeable devant n’importe quelle fonction de la forme quand n tend vers l'infini et pour un polynôme à une variable. C'est presque toujours par rapport à cette classe qu'on se réfère en pratique, considérant qu'il s'agit d'un bon modèle des capacités des calculateurs réels. La collection des fonctions négligeables pour un paramètre est notée . C'est une collection stable par les opérations arithmétiques (addition, multiplication) et par composition. En d'autres termes, aucun algorithme terminant en un temps polynomial ne permet de construire une fonction non négligeable à partir seulement d'appels à une fonction négligeable. Cette propriété, à rapprocher des infinitésimaux, permet de construire des arguments hybrides : une succession de jeux dans lesquels l'avantage de l'adversaire est une fonction négligeable (d'un paramètre de sécurité), et qui trace un pont progressif entre une situation idéale et une situation réelle. L'accumulation de ces avantages négligeables, par compositionnalité, reste négligeable.