Вероятностные вычисления. Классы RP, coRP, ZPP, BPP/Задачи/amplify-when-specific-error-bounded/Решение Гилязева Руслана

Материал из DISCOPAL
Перейти к: навигация, поиск

Запустим A n раз. Получим множество исходов. Устремим n к бесконечности. Тогда вероятность того, что f(x) встречается в множестве большее число раз, чем любое другое число стремится к 1 (т. к. вероятность появления любого неправильного ответа меньше чем вероятность появления правильного хотя бы на 1/12). Поэтому существует N, такое, что для любого x(следует из того что есть "зазор" вероятности в 1/12 для любого входа): Prob(в множестве из N исходов самый популярный элемент f(x)) > 0.5. Запустим A N раз и выведем самый популярный элемент. Т. е. можно сделать из A полезный алгоритм.

StasFomin (обсуждение) 12:56, 19 мая 2015 (MSK): Ну тут нужно не просто соображение, что «чем больше тем лучше», а оценки, для определения этого N. Иначе, какой это «алгоритм»?