Вопросы с тегом «randomness»

16
Какова мотивация определения псевдослучайного в Nisan / Wigderson?

Я читаю классическую «Твердость против случайности» Нисана и Вигдерсона. Пусть и исправим функцию . Они определяют семейство функций как псевдослучайное в случае, если для каждой схемы размера мы имеемl : N → N G = { G n : B l ( n ) → B n }B={0,1}B={0,1}B=\{0,1\}l:N→Nl:N→Nl\colon \mathbb{N} \to...

15
Обзоры по конструкции генератора псевдослучайных чисел?

Я заинтересован в генерации псевдослучайных чисел для криптографии. Помимо главы 5 Менезес / Oorschot / Vanstone ; Глава 8 Стинсона ; и глава 3 Goldreich , где еще я могу найти больше? Меня интересуют общие принципы проектирования PRNG (желательные свойства, тесты и т....

15
Случайная монотонная функция

В статье Разборова-Рудича « Естественные доказательства» , стр. 6, в той части, в которой они обсуждают, что есть «сильные доказательства нижних границ против моделей монотонных схем» и как они вписываются в картину, есть следующие предложения: Здесь проблема не в конструктивности - все свойства,...

15
Природные теоремы доказаны только «с высокой вероятностью»?

Существует множество ситуаций, когда рандомизированное «доказательство» намного проще, чем детерминированное доказательство, каноническим примером является проверка полиномиальной идентичности. Вопрос : Существуют ли естественные математические «теоремы», в которых рандомизированное доказательство...

13
Сколько независимости требуется для отдельного сцепления?

Если шаров равномерно размещены в n корзинах случайным образом, то в самой тяжелой загруженной корзине с высокой вероятностью будет O ( lg n / lg lg n ) шариков. В «Сложности простого хэширования табуляции» Патрашку и Торуп упоминают, что «границы Черноффа-Хёффдинга для приложений с ограниченной...

13
Каково смещение случайных многочленов с низкой степенью над GF (2)?

У меня есть вопрос, касающийся полиномов и вероятностей низкой степени: какова (асиптотическое поведение) вероятность того, что случайный * полином ppp по GF (2) со степенью и n переменных имеет .≤d≤d\le...

12
Псевдослучайный генератор для конечных автоматов

Пусть будет константой. Как мы можем с уверенностью построить псевдослучайный генератор, который обманывает конечные автоматы d- состояния?dddddd Здесь, -state имеет конечные автоматы d узлов, начальный узел, набор узлов , представляющие принимают состояния, и две направленных ребер помечены 0, 1 ,...

12
Когда рандомизация перестает помогать в PSPACE

Известно, что добавление рандомизации с ограниченной ошибкой в ​​PSPACE не добавляет мощности. То есть BPPSAPCE = PSPACE. Известно, что P = BPP известно, но известно, что .Б Пп⊆ Е2∩ Π2Впп⊆Σ2∩Π2BPP\subseteq \Sigma_2\cap \Pi_2 Таким образом, возможно (хотя предполагается, что оно ложно), что...

12
Рандомизированная полиномиальная иерархия?

Интересно, что произойдет, если в определении (полиномиальная иерархия, см., Например, здесь ) роль будет заменена на ?PHPHPHNPNPNPRPRPRP Кажется, мы все еще можем построить иерархию, так же, как строится , просто используя везде вместо и вместо . Давайте назовем это рандомизированной...

12
Сумма независимых экспоненциальных случайных величин

Можем ли мы доказать точный результат концентрации на сумме независимых экспоненциальных случайных величин, т.е. пусть - независимые случайные величины, такие что . Пусть . Можем ли мы доказать оценки вида . Это следует непосредственно, если мы используем дисперсионную форму границ Чернова и,...

12
Какое точное определение Random K-SAT?

Есть 4 различных ограничения, которые мы можем иметь при определении Random K-SAT. 1) Общее количество литералов в заданных предложениях в точности равно K или AT большинству K 2) Данный литерал может использоваться с заменой или без замены в одном и том же предложении (A или A или A) 3) Данная...

12
Детерминированное снижение ошибок, современное состояние?

Предположим, что у каждого есть рандомизированный (BPP) алгоритм AAA использующий рrr битов случайности. Естественные способы увеличить вероятность успеха до 1 - δ1−δ1-\delta для любого выбранного δ> 0δ>0\delta>0 : Независимые прогоны + голосование большинством: прогоните AAA независимо T= Θ...

12
Измерение случайности формул CNF

Широко известно, что формулы CNF можно условно разделить на 2 широких класса: случайный и структурированный. Структурированные формулы CNF, в отличие от случайных формул CNF, демонстрируют некоторый порядок, демонстрируя паттерны, которые вряд ли могут произойти случайно. Тем не менее, можно найти...

11
Рандомизированные алгоритмы с использованием стека

Я разработал новую методику дерандомизации, которая нацелена на рекурсивные рандомизированные алгоритмы (или) более общие рандомизированные алгоритмы, которые используют стек. К сожалению, я не смог найти естественные рандомизированные алгоритмы для применения моих методов. Рекурсивные цепи Маркова...

10
Какова самая быстрая из известных симуляций БПП с использованием алгоритмов Лас-Вегаса?

BPPBPP\mathsf{BPP} иZPPZPP\mathsf{ZPP} - два основных класса вероятностной сложности. BPPBPP\mathsf{BPP} - это класс языков, определяемых вероятностными алгоритмами Тьюринга за полиномиальное время, где вероятность возврата неправильного ответа ограничена, т. Е. Вероятность ошибки не...

10
Возможно ли, что детерминистская псевдослучайность сильнее параллельности случайности?

Пусть класс BPNC (комбинация и ) будет параллельным алгоритмом глубины логарифма с ограниченной вероятностью ошибки и доступом к случайному источнику (я не уверен, что у него другое имя). Определите класс DBPNC аналогичным образом, за исключением того, что все процессы имеют произвольный доступ к...

10
Единообразный способ количественного определения «ветвления» в недетерминированных, вероятностных и квантовых вычислениях?

Хорошо известно, что вычисление недетерминированной машины Тьюринга (NTM) представляется в виде дерева конфигураций, основанного на начальной конфигурации. Любой переход в программе представлен ссылкой «отец-ребенок» в этом дереве. Подобные деревья также могут быть построены для визуализации...

10
Известно ли ?

Обратное включение очевидно, так же как и тот факт, что любой самоустраиваемый язык NP в BPP также находится в RP. Известно ли, что это также относится к несаморедуцируемым языкам...