Random self-reducibility
description: 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 @fr
subject: Category:Randomized algorithms
description: property of an algorithm that implies that its worst-case complexity is equal to its mean-complexity
hypernym: Rule