Издательство: | Книга по требованию |
Дата выхода: | июль 2011 |
ISBN: | 978-6-1313-6693-2 |
Объём: | 88 страниц |
Масса: | 153 г |
Размеры(В x Ш x Т), см: | 23 x 16 x 1 |
High Quality Content by WIKIPEDIA articles! Random self-reducibility (RSR): A good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances.If a function f evaluating any instance x can be reduced in polynomial time to the evaluation of f on one or more random instances yi, then it is self-reducible (this is also known as a non-adaptive uniform self-reduction). In a random self-reduction an arbitrary worst-case instance x in the domain of f is mapped to a random set of instances y1, ..., yk. This is done so that f(x) can be computed in polynomial time, given the coin-toss sequence from the mapping, x, and f(y1), ..., f(yk). Therefore, taking the average with respect to the induced distribution on yi, the average-case complexity of f is the same (within polynomial factors) as the worst-case randomized complexity of f.
Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.