Изменения

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

Алгоритм Бен-Ора

562 байта добавлено, 20:00, 3 июня 2019
Оценки
Без доказательства.
Но у нас есть недетерминированный алгоритм в асинхронной системе с сильным противником с вероятностью завершения за конечное число шагов, равной единице.
Правда, среднее время работы экспоненциально: $O(2^N)$, потому что нам надо, чтобыслучайными флуктуациями получилось достаточно много одинаковых битов.Примерная причина: мы хотим случайно получить ситуацию, в которой есть больше $\frac N 2$ одинаковых битов из каких-то $N - f$, которые нам подсунул противник). Алгоритм не очень практичный, но интересный: показывает, как использовать монетку.
292
правки

Навигация