Проблемы в P с заметно более быстрыми рандомизированными алгоритмами

Есть ли в проблемы, в которых рандомизированные алгоритмы бьют нижние оценки для детерминированных алгоритмов? Конкретнее, знаем ли мы для которого ? Здесь \ mathsf {PTIME} (f (n)) означает набор языков, разрешимых рандомизированным TM с постоянной (одной или двухсторонней) ошибкой в f (n) шагах. k D T I M E ( n k ) ⊊ P T I M E ( n k ) P T I M E ( f ( n ) ) f ( n $\mathsf{P}$$k$$\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)$$\mathsf{PTIME}(f(n))$$f(n)$

Покупает ли случайность что-нибудь внутри $\mathsf{P}$ ?

Чтобы было ясно, я ищу что-то, где различие асимптотическое (предпочтительно полиномиальное, но я бы согласился на полилогарифмическое), а не просто постоянное.

Я ищу алгоритмы асимптотически лучше в худшем случае. Алгоритмы с лучшей ожидаемой сложностью не то, что я ищу. Я имею в виду рандомизированные алгоритмы, как в RP или BPP, а не в ZPP.

Полиномиальное тестирование идентичности допускает алгоритм рандомизированного полиномиального времени (см. Лемму Шварца-Циппеля ), и в настоящее время у нас нет детерминированного полиномиального времени или даже субэкспоненциального алгоритма времени.

Оценка игрового дерева Рассмотрим полное двоичное дерево сконечными узлами, каждый из которых хранит значение 0/1. Внутренние узлы содержат логические элементы ИЛИ / И на альтернативных уровнях. Используя аргумент противника, можно доказать, что каждый детерминистический алгоритм должен был бы исследоватьлистовые узлыв худшем случае. Однако существует простой рандомизированный алгоритм, который требует ожидаемого времени выполнения Посмотрите на слайды 14-27 доклада.Ω ( n ) O ( n 0,793$n$$\Omega{(n)}$$O(n^{0.793})$

Забывчивая маршрутизация на гиперкубе. Рассмотрим куб визмерениях, содержащий вершин. Каждая вершина имеет пакет данных и пункт назначения, в который она хочет в конечном итоге доставить пакет. Пункт назначения всех пакетов различен. Даже для этого было доказано, что любая детерминистическая стратегия маршрутизации будет проходитьшагов. Тем не менее, существует простая рандомизированная стратегия, которая с высокой вероятностью завершится в ожидаемыхшагах.N = 2 n Ω ($n$$N=2^n$O(n$\Omega{\big(\sqrt{\frac{N}{n}}\big)}$ $O(n)$

Обратите внимание, что в рандомизированных алгоритмах ожидаемая стоимость с высокой вероятностью (как, например, для ) эквивалентно наихудшему случаю на практике.P r [ F ( n ) > 10 ⋅ E ( F ( n ) ) ] < $E(F(n))$ $Pr[F(n) > 10 \cdot E(F(n))] < \frac{1}{n^2}$

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

Рассмотрим любой вероятностный алгоритм . Получите детерминированный алгоритм , зафиксировав случайную ленту для в . Тогда для всех .B A 0 ∞ T B ( n ) ≤ T A ( n ) $A$$B$$A$$0^\infty$$T_B(n) \leq T_A(n)$$n$

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

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

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

Вы спрашиваете, в чем связь? Хорошо, рассмотрим любой рандомизированный алгоритм который эффективно решает некоторые проблемы. Он опирается на случайные монеты: случайные биты, полученные из истинно-случайного источника. Теперь предположим, что мы берем генератор псевдослучайного качества криптографического качества и заменяем источник случайных чисел выходным сигналом генератора псевдослучайных чисел. Вызвать полученный алгоритм . Обратите внимание , что является детерминированным алгоритмом и его продолжительность составляет примерно такие же , как .A ′ A ′$A$$A'$$A'$$A$

Кроме того, если криптографический PRNG безопасен, эвристически мы должны ожидать, что будет хорошим алгоритмом, если :$A'$$A$

• Например, если - это алгоритм Лас-Вегаса (он всегда выводит правильный ответ и быстро заканчивается с высокой вероятностью), то будет довольно хорошим детерминированным алгоритмом (всегда выводит правильный ответ и быстро завершается для большинства входных данных) ,A $A$$A'$

• В качестве другого примера, если представляет собой алгоритм Монте-Карло (детерминированное время выполнения и выдает правильный ответ с вероятностью, по крайней мере, ), то будет довольно хорошим детерминированным алгоритмом (детерминированное время выполнения и выдает правильный ответьте на долю от всех входов). 1 - ε A 1 - $A'$$1-\varepsilon$$A$$1-\varepsilon$

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

Детали конструкции: Вот как работает . На входных , он выводит семя для криптографической PRNG как функции (например, с помощью хэш ), а затем имитирует , с использованием выходного сигнала криптографической PRNG в качестве монет для . Например, конкретная реализация должна была бы установить , а затем использовать в качестве начального числа для AES256 в режиме счетчика или некоторого другого криптографического PRNG. Мы можем доказать приведенные выше утверждения в рамках модели случайного оракула. x x x A ( x ) A k = SHA256 ( x ) $A'$$x$$x$$x$$A(x)$$A$$k=\text{SHA256}(x)$$k$

Если вы недовольны идеей, что « может выдавать неправильные результаты на небольшой части входных данных, это можно исправить. Если вы повторяете « несколько раз и принимаете большинство голосов, вероятность ошибки уменьшается экспоненциально быстро в количестве итераций. Таким образом, повторяя постоянное число раз, вы можете получить вероятность ошибки ниже , что означает, что шансы на то, что вы натолкнетесь на вход когда алгоритм выводит неправильный ответ, являются чрезвычайно малыми (меньше шансов получить удар молнией несколько раз подряд). Более того, с помощью конструкции, которую я дал выше, шансы, что противник может даже найти вход' Ε 1 / 2 256 х х $A'$$A'$$\varepsilon$$1/2^{256}$$x$$x$ где дает неправильный ответ, может быть сделан очень маленьким, так как это потребовало бы нарушения безопасности хэша SHA256. (Технически это требует, чтобы модель случайного оракула оправдывалась, поэтому это означает, что должен быть выбран как «независимый» от SHA256, а не с жестким кодом в его вычислениях, связанных с SHA256, но почти все реальные алгоритмы будут удовлетворять этому требованию .)$A'$$A$

Если вам нужна более сильная теоретическая основа, вы можете выполнить итерацию раз и получить вероятность ошибки ниже , где - длина ввода . Теперь доля битных входов, где дает неправильный ответ, строго меньше . Но есть только возможных битных входов, и на каждом из либо правильно, либо неправильно, поэтому из этого следует, что нет входа, где неверно: правильно на всех входах, и это верно , ЕслиΘ ( п ) 1 / 2 п п х п ' 1 / 2 л 2 н п ' ' т ( п ) ' Θ ( п ⋅ т ( п ) ) A $A$ $\Theta(n)$$1/2^n$$n$$x$$n$$A'$$1/2^n$$2^n$$n$$A$$A'$$A'$$A$выполняется за время , затем выполняется за время , поэтому немного медленнее, чем но не слишком медленнее. Это содержание доказательства Адлемана, что BPP содержится в P / poly. Для практических целей это, вероятно, излишне, но если вам нравятся чистые доказательства, которые избегают криптографических предположений, или если вы подходите к этому с точки зрения теоретика, тогда вам может понравиться эта версия лучше.$t(n)$$A'$$\Theta(n \cdot t(n))$$A'$$A$

Для получения более подробной информации о последних теоретических соображениях и дополнительных проблемах, когда мы знаем эффективный рандомизированный алгоритм, но мы не знаем ни одного детерминированного алгоритма, который мы можем доказать как эффективный, см. Https://cstheory.stackexchange.com/q/31195. / 5038

Итак, для любой проблемы, в которой нам известен эффективный рандомизированный алгоритм, мы также знаем детерминированный алгоритм, который, вероятно, эффективен на практике, но в настоящее время мы не знаем, как доказать, что он эффективен. Одна из возможных интерпретаций заключается в том, что мы не очень хорошо разбираемся в алгоритмах.