Когда рандомизация ускоряет алгоритмы, и это «не должно»?

39

Доказательство Адлеманом того, что BPP содержится в P/poly показывает, что если существует случайный алгоритм для задачи, который выполняется во времени на входах размера , то также существует детерминированный алгоритм для задачи который запускается за время на входах размера [алгоритм запускает рандомизированный алгоритм на независимых строках случайности. Должна быть случайность для повторного алгоритма, который хорош для всехn Θ ( t ( n ) n ) n Θ ( n ) 2 nt(n)NΘ(T(N)N)NΘ(N)2Nвозможные входы. Детерминированный алгоритм является неоднородным - он может вести себя по-разному для разных входных размеров. Таким образом, аргумент Адлемана показывает, что - если не заботиться об однородности - рандомизация может только ускорить алгоритмы с коэффициентом, линейным по размеру входных данных.

На каких конкретных примерах рандомизация ускоряет вычисления (насколько нам известно)?

Одним из примеров является проверка полиномиальной идентичности. Здесь вход представляет собой арифметическую схему n-размера, вычисляющую многочлен m-вариации над полем, и задача состоит в том, чтобы выяснить, является ли многочлен тождественно нулевым. Рандомизированный алгоритм может оценивать полином по случайной точке, в то время как лучший детерминированный алгоритм, который мы знаем (и, возможно, лучший из существующих), оценивает полином по многим точкам.

Другим примером является минимальное остовное дерево, где лучшим рандомизированным алгоритмом Каргера-Кляйна-Тарьяна является линейное время (а вероятность ошибки экспоненциально мала!), В то время как лучший детерминированный алгоритм Шазеля выполняется во времени О(мα(м,N)) ( α - обратная функция Аккермана, поэтому ускорение рандомизации действительно мало). Интересно, что Петти и Рамачандран доказали, что если существует неравномерный детерминированный линейный алгоритм времени для минимального остовного дерева, то также существует единый детерминированный линейный алгоритм времени.

Какие еще примеры? Какие примеры вы знаете, где ускорение рандомизации велико, но это возможно только потому, что мы еще не нашли достаточно эффективных детерминированных алгоритмов?

Дана Мошковиц
источник
Вы всегда можете преобразовать любой рандомизированный алгоритм в детерминированный алгоритм, заменив генератор случайных чисел на генератор псевдослучайного качества криптографического качества. При вероятных криптографических предположениях, которые, насколько нам известно, действительны, это прекрасно работает. Поэтому мой ответ будет таким: «насколько нам известно, ответ таков: таких реальных проблем не существует». (Другими словами, насколько нам известно, разрыв во времени выполнения отражает нашу неспособность доказать жесткие границы времени выполнения, а не какую-либо реальную базовую разницу.)
DW
1
При разумных допущениях жесткости вы можете подать случайность алгоритма из генератора псевдослучайных данных, однако, чтобы фактически получить из этого детерминированный алгоритм, вам нужно запустить алгоритм на всех возможных начальных значениях. Это взрывает время выполнения!
Дана Мошковиц
В дополнение к точке зрения Даны, я думаю, что для дерандомизации BPP PRG должен работать больше времени, чем первоначальный алгоритм (хотя я не знаю, какой должен быть разрыв). Кроме того, это может иллюстрировать (фундаментальный?) Разрыв между достоверностью и экспоненциально высокой достоверностью: достаточно повторить рандомизированный алгоритм раз (для любой константы c ), чтобы получить вероятность правильности 2 - O ( c ) , но для детерминированной версии требуется проверить все полиномиально много семян. сс2-О(с)
Усул
@DanaMoshkovitz, это зависит от того, подходите ли вы к этому с теоретической или практической точки зрения. С точки зрения практикующего, нет, вам не нужно этого делать. См. Конструкцию, которую я обрисовал в общих чертах, в cs.stackexchange.com/a/41723/755 , которая запускает алгоритм только для начальных чисел . В рамках модели случайного оракула можно показать, что асимптотическое время выполнения не увеличивается, и никакой вычислительно ограниченный противник, вероятно, не сможет найти какие-либо входные данные для алгоритма, где алгоритм дает неправильный ответ. Это, вероятно, достаточно хорошо для всех практических целей. О(1)
DW

Ответы:

28

Я не знаю , является ли рандомизация «должен» или «не должен» помочь, однако, целое испытание на простоту может быть сделано во времени с использованием рандомизированы Миллера-Рабина, в то время, насколько я знаю, самый известный детерминированные алгоритмы ~ о ( п 4 ) при условии , GRH (детерминированный Миллера-Рабина) или ~ о ( п 6 ) безусловно (варианты АКС).O~(n2)O~(n4)O~(n6)

Эмиль Йержабек поддерживает Монику
источник
Хотя есть основания полагать , что самый маленький свидетель на составной имеет порядок журнал N журнал журнал N , который дал бы ~ О ( п 3 ) алгоритм. Но это остается недоказанным даже при стандартных теоретико-числовых гипотезах, таких как варианты RH. NlogNloglogNO~(n3)
Эмиль Йержабек поддерживает Монику
Проблема в том же духе - проверка полиномиальной неприводимости над конечными полями, где опять-таки известные детерминированные алгоритмы имеют худшие оценки, чем рандомизированные алгоритмы, но я не помню деталей.
Эмиль Йержабек поддерживает Монику
19

Старый пример - вычисление объема. Учитывая многогранник, описываемый оракулом членства, существует рандомизированный алгоритм, работающий за полиномиальное время для оценки его объема с коэффициентом но ни один детерминированный алгоритм не может даже приблизиться безоговорочно .1+ϵ

Первым примером такой рандомизированной стратегии были Дайер, Фриз и Каннан, а результат твердости для детерминированных алгоритмов - Барани и Фюреди. Алистер Синклер имеет хорошие лекционные заметки по этому вопросу .

Я не уверен, что полностью понимаю «и это не должно» часть вопроса, поэтому я не уверен, что это отвечает всем требованиям.

Суреш Венкат
источник
1
Я знал о методе MCMC, но не об этой нижней границе, и я весьма удивлен (я думал, что все, что было известно, это # ​​P-твердость). Статья «Вычислить объем - это сложно », доступна на веб-странице Фюреди , и они дают нижнюю границу, по существу, того, насколько хорошо объем может быть аппроксимирован. [n/logn]n
Джереми Кун
9

я не знаю, отвечает ли это на ваш вопрос (или хотя бы его часть). Но в реальных примерах, где рандомизация может обеспечить ускорение, речь идет о задачах оптимизации и связи с теоремой об отсутствии бесплатного обеда ( NFL ) .

Есть статья «Возможно, не бесплатный обед, но, по крайней мере, бесплатная закуска», где показано, что использование алгоритмов рандомизации (оптимизации) может иметь лучшую производительность.

Аннотация:

Часто утверждается, что эволюционные алгоритмы превосходят другие методы оптимизации, в частности, в ситуациях, когда о целевой функции, подлежащей оптимизации, известно немного. В отличие от этого Wolpert и Macready (1997) доказали, что все методы оптимизации имеют одинаковое поведение - в среднем по всем где X и Yе:ИксYИксYконечные множества. Этот результат называется «Теорема об отсутствии бесплатного обеда». Здесь представлены разные сценарии оптимизации. Утверждается, что сценарий, на котором основана теорема об отсутствии бесплатного обеда, не моделирует реальную оптимизацию. Для более реалистичных сценариев утверждается, почему методы оптимизации отличаются по своей эффективности. Для небольшого примера это утверждение доказано.

Ссылки:

  1. Нет бесплатных теорем об обеде для оптимизации (оригинальная теорема НФЛ для оптимизации)
  2. Возможно, не бесплатный обед, но, по крайней мере, бесплатная закуска
  3. Безобеденный обед и длина описания (показывает, что результаты НФЛ верны для любого подмножества из набора всех возможных функций, если F замкнуто при перестановке, кубок )FF
  4. О классах функций, для которых верны результаты No Free Lunch (доказано, что доля подмножеств, являющихся чашками , пренебрежимо мала)
  5. Два широких класса функций, для которых результат без свободного обеда не выполняется (показывает, что результат NFL не применяется к набору функций, когда длина описания функций достаточно ограничена)
  6. Непрерывные обеды бесплатны плюс разработка оптимальных алгоритмов оптимизации (показывает, что для непрерывных областей [официальная версия] НФЛ не выполняется. Эта теорема о бесплатном обеде основана на формализации концепции случайных функций пригодности посредством случайных полей )
  7. За пределами бесплатного обеда: реалистичные алгоритмы для произвольных классов задач (показывает, что «.. [a] все нарушения теорем об отсутствии бесплатного обеда могут быть выражены как неоднородное равномерное распределение по подмножествам задач, которые являются кубками »)
  8. Метаэвристические алгоритмы на основе роя и теоремы об отсутствии свободного обеда (далее «[..t]», результаты для неревизионных упорядоченных по времени итераций могут быть неверными для случаев повторных пересмотров, поскольку повторные пересмотры нарушают важное предположение чашка, необходимая для доказательства теорем НФЛ (Marshall and Hinton, 2010) ")
  9. Нет бесплатного обеда и алгоритмическая случайность
  10. Отсутствие бесплатного обеда и тестов (теоретико-множественный подход, который обобщается на критерии, не специфичные для кубка , но при этом отмечается, что (нетривиальные) рандомизированные алгоритмы могут в среднем опережать детерминированные алгоритмы "[...] было продемонстрировано, что вероятность неадекватна для подтверждения неограниченных результатов НФЛ в общем случае. [..] эта статья отказывается от вероятности, отдавая предпочтение теоретико-множественной структуре, которая устраняет теоретико-мерные ограничения, полностью исключая вероятность ")

Резюме о бесплатных обедах (и бесплатных обедах) от David H. Wolpert, Сколько стоит ужин? ( обратите внимание, что теоремы типа НФЛ никогда не указывают фактическую « цену » из-за их типа доказательства)

специально для обобщенной оптимизации (GO):

  1. Два пространства и Z . Например, X - это входы, Z - это распределение по выходам.ИксZИксZ

  2. Фитнес-функция е:ИксZ

  3. ме

    dm={dm(1),dm(2),...,dm(m)}
    t
    dm(t)={dmX(t),dmZ(t)}
    dmZ(t)f[dmX(t)]
  4. a={dtdmX(t):t=0..m}

  5. C(f,dm)

  6. C(.,.)

CfCfC(f,dm)f=f

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

  1. В контексте оптимизации (хотя и не ограничиваясь этим) рандомизированная процедура поиска может в среднем избежать локальных экстремумов лучше, чем детерминированный поиск, и достичь глобальных экстремумов.
  2. 2AAAAA
Никос М.
источник
1

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

Т ....
источник
-5

Если у вас есть алгоритм, использующий рандомизацию, вы всегда можете заменить его детерминированным алгоритмом, использующим псевдослучайные числа: возьмите описание проблемы, вычислите хеш-код, используйте этот хеш-код в качестве начального числа для хорошего генератора псевдослучайных чисел , На практике это действительно то, что может случиться, когда кто-то реализует алгоритм с использованием рандомизации.

Если мы пропустим хеш-код, то разница между этим алгоритмом и алгоритмом, использующим истинную рандомизацию, состоит в том, что я могу предсказать последовательность генерируемых случайных чисел, и я могу создать такую ​​проблему, что предсказанное случайное число, примененное к моей проблеме, всегда будет принять самое худшее решение. Например, для быстрой сортировки с псевдослучайным стержнем я мог бы создать входной массив, в котором псевдослучайный стержень всегда найдет наибольшее возможное значение в массиве. С настоящей случайностью это невозможно.

С помощью хеш-кода мне было бы очень трудно построить проблему, когда псевдослучайные числа приводят к худшим результатам. Я все еще могу предсказать случайные числа, но если я изменю проблему, последовательность псевдослучайных чисел полностью изменится. Тем не менее, было бы почти невозможно доказать, что я не могу построить такую ​​проблему.

gnasher729
источник
Я новичок в cstheory.SE. Итак, downvoters - что не так с этим ответом?
Галдре
3
Две вещи неправильны: (1) мы не знаем, как вообще построить псевдослучайные числа, (2) даже когда мы знаем, как их построить, они вычислительно дороги. Псевдослучайные числа, используемые на практике, не гарантируют теоретической работы; все, что мы знаем, это то, что они работают эмпирически. (Действительно, большинство используемых ГПНГ могут быть сломаны, поэтому они вообще небезопасны для использования, только если вы специально не пытаетесь их сломать.)
Юваль Фильм
2
cstheory.se - это теоретическая информатика *, а не практика программирования. Как ни крути, эти две области совершенно разные.
Юваль Фильмус
2
@YuvalFilmus: Генератор переменного шага, изобретенный К. Гюнтером в 1987 году, еще не сломан (публичного перерыва пока нет, и я сомневаюсь, что АНБ также его сломало). Двадцать восемь лет - это долгое время, чтобы оставаться непрерывным, я поражен тем, что такой простой генератор (три LFSR и один вентиль XOR, насколько это просто?) Еще не сломан и не используется чаще.
Уильям Хёрд
2
@WilliamHird: в зависимости от определения «сломанный», кажется, что он фактически был сломан (более или менее в той же степени, что и родственное, более эффективное и широко используемое семейство A5 / x). См. Crypto.stackexchange.com/a/342 .
Эмиль Йержабек поддерживает Монику