Я пытаюсь как самоучка прочитать главу 4 «Основы криптографии» Одеда Голдрейха (чтобы вы могли «настроить» свои ответы, у меня есть инженерное образование).
Если я правильно понимаю, даю идеальный симулятор $S_1$ возможность остановки не проблема, потому что мы можем определить симулятор $S_2$ который повторяется $S_1$ скажем $n$ раз, выводя результат первого не останавливающегося $S_1$ итерация или "фиктивный" результат, если ВСЕ $S_1$ итерации останавливаются. Таким образом, вероятность $S_2$ вывод фиктивного результата можно сколько угодно уменьшать с ростом $n$.
$S_1$ вероятность остановки ограничена сверху $1/2$, но почему? Мне кажется, каждый $S_1$ вероятность остановки $<1$ будет понижен в сторону $0$ по достаточно большому $n$. Более того, симулятор кажется совершенно отличным аргументом от вероятностей полноты/обоснованности, где строгие $1/2$ порог оправдывается правилом большинства, применяемым к этой (другой) стратегии повторений.
И, кстати, есть ли смысл выбирать $S_1$ количество повторений $n$ совпадать с другим числом повторений, необходимых для перехода от слабой полноты/правильности к более сильным? Или числа двух видов итераций взаимно независимы? Я предполагаю, что это сомнение исходит из того, что я смущен тем, что $S_2$ это симулятор для слабого IP, или для более сильного IP...
Спасибо!
