Случайные соображения генератора при проектировании рандомизированных алгоритмов

Question

Хорошо известно, что эффективность рандомизированных алгоритмов (по крайней мере, в BPP и RP) зависит от качества используемого случайного генератора. Идеальные случайные источники недоступны на практике. Хотя доказано, что для всех $ 0 < delta leq frac {1} {2} $ the Identities bpp = $ delta $ -bpp и rp = $ delta $ -rp удерживается, не правда, что оригинал Алгоритм, используемый для префектного случайного источника, может быть непосредственно использовать также для источника $ delta $ -random. Вместо этого нужно сделать некоторую симуляцию. Это моделирование является полиномом, но полученный алгоритм не так эффективен, как оригинальный.

Более того, насколько мне известно, случайные генераторы, используемые на практике, обычно даже не являются даже $ delta $-sources, а источники псевдолупита, которые могут вести себя чрезвычайно плохо в худшем случае.

Согласно с Википедия:

В общей практике рандомизированные алгоритмы аппроксимируются с использованием генератора псевдордомов вместо истинного источника случайных битов; Такая реализация может отклониться от ожидаемого теоретического поведения.

Фактически, реализации рандомизированных алгоритмов, которые я видел до сих пор, были просто реализацией алгоритмов для идеальных случайных источников, работающих с использованием источников псевдорядомы.

Мой вопрос: если есть какое -либо оправдание этой общей практики. Есть ли какие -либо основания ожидать, что в большинстве случаев алгоритм вернет правильный результат (с вероятностями, как в BPP. RP. RP)? Как может быть формализовано «приближение», упомянутое в цитате из Википедии? Может ли упомянутое отклонение быть каким -то образом оценить, по крайней мере, в ожидаемом случае? Можно ли утверждать, что рандомизированный алгоритм Монте-Карло, работающий на идеальном случайном источнике, превратится в стохастический алгоритм хорошо приобретенного в поле зрения при запуске на источнике псевдорандома? Или есть другие подобные соображения?

Answer 1

Вот одно хорошее оправдание. Предположим, что вы используете генератор псевдорядомов криптографического псевдома псевдома для генерации случайных битов, необходимых для некоторого рандомизированного алгоритма. Тогда полученный алгоритм будет продолжать работать, пока крипто -алгоритм безопасен.

А Генератор псевдорандных номеров криптографии является стандартным инструментом из криптографии, который принимает короткое семя (скажем, 128 бит истинной случайности) и генерирует неограниченное количество псевдорандомов. Он поставляется с очень сильной гарантией безопасности: до тех пор, пока основной криптографический примитив не сломается, то псевдоряндомические биты будут совершенно неразличимы от битов истинного рандома любым возможным процессом (и, в частности, никакой эффективной алгоритм не может отличить его выход из последовательности истинных случайных битов). Например, мы можем получить гарантию, которая говорит: если факторинг труд (или, если RSA безопасен; или, если AES безопасен), то это хороший псевдорандомов.

Это действительно очень сильная гарантия, поскольку, как считается, очень трудно сломать эти криптографические примитивы. Например, если вы сможете найти эффективный способ учитывать очень большое количество, то это будет результатом прорыва. Для всех практических целей вы можете действовать так, как будто криптографические примитивы нерушимы. Это означает, что для всех практических целей вы можете действовать так, как будто вывод криптографического генератора псевдорядома псевдора в основном такой же, как и последовательность битов истинного земли. В частности, это хороший источник случайности, необходимой рандомизированному алгоритму.

(Я заверил тот факт, что, чтобы использовать крипто-силу PRNG, вам все равно нужно найти 128 кусочков истинной случайности самостоятельно, чтобы сформировать семя. Но обычно это не сложно, и действительно, есть криптографические инструменты Чтобы помочь с этой задачей.)

На практике получить чрезвычайно хорошие псевдорандомовые биты так же просто, как

$ cat /dev/urandom

Answer 2

Хорошо известно, что эффективность рандомизированных алгоритмов (по крайней мере, в BPP и RP) зависит от качества используемого случайного генератора. Я должен не согласиться. Что дает вам хороший ансамбль последовательности псевдурандомов, так это гарантия на производительность алгоритма, выполняя случайную последовательность из ансамбля по сравнению с случайной последовательности. Если у вас нет такой гарантии, вы не можете сделать вывод, что алгоритм будет работать плохо - вы просто не знаете.

Есть ли оправдание этой общей практики? Оно работает.

Можно ли утверждать, что рандомизированный алгоритм Монте-Карло, работающий на идеальном случайном источнике, превратится в стохастический алгоритм хорошо приобретенного в поле зрения при запуске на источнике псевдорандома? Теория сложности страдает от двух недостатков. Первым является то, что очень сложно что -либо доказать (например, P vs. NP открыт). Вторым является то, что в основном это касается анализа наихудшего случая. Вместе эти два ограничения исключают теорию сложности как хорошую модель для поведения алгоритмов на практике.