Random self-reducibility
propriété d'un algorithme qui implique que la complexité au pire est égale à la complexité en moyennt : une instance quelquonque du problème cible peut être réduite en temps polynomial vers une ou plusieurs instances aléatoires
property of an algorithm that implies that its worst-case complexity is equal to its mean-complexity