Fonction négligeable

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.