Алгоритм, поведение которого определяется его входом и генератором, генерирующим равномерно случайные числа.
Доказательство Адлеманом того, что BPPBPPBPP содержится в P/polyP/polyP/poly показывает, что если существует случайный алгоритм для задачи, который выполняется во времени на входах размера , то также существует детерминированный алгоритм для задачи который запускается за время на входах размера...
Многие считают, что . Однако мы только знаем, что находится на втором уровне полиномиальной иерархии, то есть . Шаг к показу состоит в том, чтобы сначала перевести его на первый уровень полиномиальной иерархии, то есть .BPPPNPBPP=P⊆NP\mathsf{BPP} = \mathsf{P} \subseteq...
Я часто слышу, что для многих задач мы знаем очень изящные рандомизированные алгоритмы, но нет или только более сложные детерминированные решения. Тем не менее, я знаю только несколько примеров для этого. Наиболее заметно Рандомизированная быстрая сортировка (и связанные геометрические алгоритмы,...
Существует ли интересный пример рандомизированного алгоритма для задачи поиска, который всегда выводит один и тот же (правильный) ответ, независимо от его внутренней случайности, но который использует случайность так, что его ожидаемое время выполнения лучше, чем время выполнения самого быстрого из...
Лог-пространство-равномерный NC содержится в детерминированном пространстве полилога (иногда пишется PolyL). Является ли лог-пространственно-равномерный RNC также в этом классе? Стандартная рандомизированная версия PolyL должна быть в PolyL, но я не вижу, чтобы (равномерный) RNC был в...
Я только что преподавал рандомизированный алгоритм сокращений по методу Каргера-Стейна в своем выпускном классе алгоритмов. Это настоящая алгоритмическая жемчужина , поэтому я не могу ее не преподавать, но она всегда расстраивает меня, потому что я не знаю других применений основной техники. (Таким...
Изменить: я выбираю ответ с наибольшим количеством баллов до 6 декабря 2012 года. Это мягкий вопрос. Концепция (детерминированных) алгоритмов восходит к BC. Как насчет вероятностных алгоритмов? В этой статье в вики в качестве первого рандомизированного алгоритма (год ???) был задан алгоритм Рабина...
Я уверен, что все знают об эксперименте Буффона с иглой в 18-м веке, это один из первых вероятностных алгоритмов для вычисления .ππ\pi Реализация алгоритма на компьютерах обычно требует использования или тригонометрической функции, которая, даже если они реализованы в виде усеченных рядов, в...
RP - это класс проблем, решаемых недетерминированной машиной Тьюринга, которая завершается за полиномиальное время, но также допускается односторонняя ошибка. P - это обычный класс задач, разрешимых детерминированной машиной Тьюринга, которая заканчивается за полиномиальное время. P = RP следует из...
Важная статья 2003 года Childs et al.представил «проблему соединенных деревьев»: проблему, допускающую экспоненциальное квантовое ускорение, которое не похоже ни на одну другую подобную проблему, о которой мы знаем. В этой задаче нам дан экспоненциально большой граф, подобный изображенному ниже,...
PPPXX\mathcal{X}AA\mathcal{A}PPPDD\mathcal{D}RR\mathcal{R}AA\mathcal{A}minA∈AEcost(A,D)≤maxx∈XEcost(R,x)for all D and R.minA∈AEcost(A,D)≤maxx∈XEcost(R,x)for all D and R.\min_{A\in\mathcal{A}}\quad\mathbb{E} cost(A,\mathcal{D}) \leq \max_{x\in\mathcal{X}}\quad\mathbb{E} cost(\mathcal{R},x)...
Для рандомизированных алгоритмов AA\mathcal{A} принимающих реальные значения, «срединный трюк» - это простой способ уменьшить вероятность отказа до любого порогового значения δ>0δ>0\delta > 0 , за счет только мультипликативного t=O(log1δ)t=O(log1δ)t=O(\log\frac{1}{\delta})накладные расходы....
Когда я преподаю границы хвоста, я использую обычную прогрессию: Если ваш тренд положительный, вы можете применить неравенство Маркова Если у вас есть независимость, а также ограниченная дисперсия, вы можете применить неравенство Чебышева Если каждый независимый rv также имеет все ограниченные...
Если - выпуклая функция, то неравенство Дженсена утверждает, что , и mutatis mutandis, когда вогнута. Очевидно, что в худшем случае вы не можете получить верхнюю границу в терминах для выпуклого , но есть ли граница, которая идет в этом направлении, если выпуклый, но не слишком выпуклый? Существует...
Пусть . Мы хотим оценить среднее значение , то есть: .f E [ f ( n ) ] = 2 - n ∑ x ∈ { 0 , 1 } n f ( x )f:{0,1}n→(2−n,1]f:{0,1}n→(2−n,1]f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]fffE[f(n)]=2−n∑x∈{0,1}nf(x)E[f(n)]=2−n∑x∈{0,1}nf(x)\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x)...
Рассмотрим следующую модель: n-битная строка r = r 1 ... r n выбирается случайным образом равномерно. Далее каждый индекс i∈ {1, ..., n} помещается в множество A с независимой вероятностью 1/2. Наконец, противнику разрешено, для каждого i∈A отдельно, перевернуть r i, если он этого хочет. Мой вопрос...
Пусть будет классом решений задач, имеющих рандомизированный алгоритм с ограниченной двусторонней ошибкой, работающий за время .O ( f ( n ) )BPTIME(f(n))BPTIME(f(n))\mathsf{BPTIME}(f(n))O(f(n))O(f(n))O(f(n)) ли нам какие-либо проблемы такие, что но ? Доказано ли его несуществование? Q ∈ B P T I M E...
Этот вопрос вдохновлен Технологическим Центром Джорджии и Центром Случайности футболкой , которая спрашивает «Рандомизировать или нет ?!» Есть много примеров, когда рандомизация помогает, особенно при работе в состязательной среде. Есть также некоторые настройки, в которых рандомизация не помогает...
Одна вещь, которую могут сделать квантовые компьютеры (возможно, даже с использованием только квантовых цепей с логарифмической глубиной BPP +), - это аппроксимировать выборку преобразования Фурье булевой -значной функции в P.± 1±1\pm 1 Здесь и ниже, когда я говорю о выборке преобразования Фурье, я...
Насколько мне известно, большинство реализаций генерации псевдослучайных чисел на практике используют такие методы, как регистры обратной связи с линейным сдвигом (LSFR) или эти алгоритмы "Mersenne Twister". Хотя они проходят множество (эвристических) статистических тестов, нет никаких...