Каждый рандомизированный алгоритм может быть смоделирован детерминированным алгоритмом за счет экспоненциального увеличения времени выполнения. Дерандомизация заключается в преобразовании рандомизированных алгоритмов в эффективные детерминированные алгоритмы.
Недавний вопрос по Гека Bennett с просьбой , был ли класс PH содержится в классе РР, получил несколько противоречивые ответы (все это правда, кажется). С одной стороны, несколько результатов оракула были даны наоборот, а с другой Скотт предположил, что ответ, вероятно, положительный, так как...
Предполагается, что случайность не расширяет возможности алгоритмов полиномиального времени, то есть предполагается, что будет выполняться. С другой стороны, случайность, по-видимому, оказывает совершенно иное влияние на сокращение полиномиального времени . По хорошо известным результатам Valiant и...
Я часто слышу, что для многих задач мы знаем очень изящные рандомизированные алгоритмы, но нет или только более сложные детерминированные решения. Тем не менее, я знаю только несколько примеров для этого. Наиболее заметно Рандомизированная быстрая сортировка (и связанные геометрические алгоритмы,...
Теорема Валианта-Вазирани говорит, что если существует алгоритм полиномиального времени (детерминированный или рандомизированный) для разграничения между формулой SAT, которая имеет ровно одно удовлетворяющее назначение, и формулой неудовлетворительного типа, - тогда NP = RP . Эта теорема доказана...
В одном предложении: подразумевает ли существование иерархии для какие-либо результаты дерандомизации?B P T I M EBPTIME\mathsf{BPTIME} но неопределенный вопрос: подразумевает ли существование иерархии для какие-либо трудные нижние границы? Влияет ли решение этой проблемы на известный барьер в...
Какие проблемы, как известно, принадлежат но не известны как принадлежащие P ?BPPBPP\mathsf{BPP}PP\mathsf P Точнее, меня интересуют независимые проблемы, то есть чьи дерандомизации, как известно, не эквивалентны. Например, известно, что дерандомизация PIT и многомерная полиномиальная факторизация...
RP - это класс проблем, решаемых недетерминированной машиной Тьюринга, которая завершается за полиномиальное время, но также допускается односторонняя ошибка. P - это обычный класс задач, разрешимых детерминированной машиной Тьюринга, которая заканчивается за полиномиальное время. P = RP следует из...
Я ищу несбалансированные расширители, которые "хороши" и "экономичны". В частности, двудольный лево-регулярный граф , , , с левой степенью является -расширителем, если для любого размером не более , число различных соседей в , по крайней мере, Известно, что вероятностный метод дает такой граф с и ....
Существует ли хороший опрос, в котором сравниваются различные экстракторы, концентраторы и суперконцентраторы и излагаются лучшие методы с точки зрения компромисса между случайностью, временем и пространством?...
С некоторыми рандомизированными алгоритмами вы можете дерандомизировать алгоритм, удаляя (при возможной стоимости во время выполнения) использование случайных битов и максимизируя некоторую нижнюю границу для цели (обычно вычисляемую с использованием факта, что теоремы об ожидаемой...
Хотя теорема Адлемана показывает, что , мне неизвестна литература, исследующая возможное включение . Какие теоретически сложные последствия будет иметь такое включение?B Q P ⊆ P / полиB P P ⊆ P / полиBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}B Q P ⊆ P / полиBQP⊆P/poly\mathsf{BQP}...
Рассмотрим следующую модель: 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...
Меня интересует явная булева функция со следующим свойством: если постоянна в некотором аффинном подпространстве , то размерность этого подпространства равна .е:0 , 1N→0 , 1е:0,1N→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}ееf о ( п )0 , 1N0,1N\\{0,1\\}^no ( n )о(N)o(n) Нетрудно показать, что...
Распределение называется ϵ- обмануть функцию f, если | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . И говорят, что он обманывает класс функций, если он обманывает каждую функцию в этом классе. Известно , что & epsi -biased пространство дурака класс паритетов над подмножествами. (см....
Я нашел книгу « Попарная независимость и дерандомизация» по этому вопросу, но она больше ориентирована на исследования, чем на учебники. Я новичок в теме «Дерандомизация», и поэтому я хотел знать, с какой ссылки начать? Я предпочитаю тот, который обсуждает литературу и историю, а также технические...
Нисан доказал в «Псевдослучайных генераторах для пространственно-ограниченных вычислений», что существует псевдослучайный генератор, который «обманывает» ограниченные в пространстве вычисления. Эта конструкция справедлива для каждого оракула (по крайней мере, для неадаптивных...
Мы знаем (на данный момент около 40 лет, спасибо Адлеману, Беннету и Джиллу), что включение BPP P / poly и еще более сильное BPP / poly P / poly имеют место. «/ Poly» означает, что мы работаем неравномерно (отдельная схема для каждой входной длины ), в то время как P без этой «/ poly» означает, что...
Adleman, FOCS'78 показал, что любая рандомизированная схема для входов длины может быть неравномерно дерандомизирована. Однако конструкция эффективно дублирует исходную схему O ( п ) раз, так что derandomized цепи больше , чем оригинал с коэффициентом O ( п ) . Есть ли более эффективная...
Каковы некоторые основные примеры успешной дерандомизации или, по крайней мере, прогресса в демонстрации конкретных доказательств достижения цели (а не связи между случайностью и жесткостью)?п= B Pппзнак равноВппP=BPP Единственный пример, который мне приходит в голову, - это тестирование AKS на...