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

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

39
Действительно генератор случайных чисел: вычислимый по Тьюрингу?

Я ищу окончательный ответ на вопрос, является ли генерация «действительно случайных» чисел вычислимой по Тьюрингу. Я не знаю, как точно сформулировать это. Этот вопрос StackExchange об «эффективных алгоритмах генерации случайных чисел» близок к ответу на мой вопрос. Чарльз Стюарт говорит в своем...

38
В чем разница между недетерминизмом и случайностью?

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

35
Эффективно вычислимая функция как контрпример к гипотезе Сарнака Мёбиуса

Недавно Гил Калай и Дик Липтон написали хорошую статью на интересную гипотезу, предложенную Питером Сарнаком, экспертом по теории чисел и гипотезе Римана. Гипотеза. Пусть - функция Мёбиуса . Предположим, что является функцией с входом в виде двоичного представления , тогда f : N → { - 1 , 1 }µ ( k...

34
Последствия содержащие

Многие считают, что . Однако мы только знаем, что находится на втором уровне полиномиальной иерархии, то есть . Шаг к показу состоит в том, чтобы сначала перевести его на первый уровень полиномиальной иерархии, то есть .BPPPNPBPP=P⊆NP\mathsf{BPP} = \mathsf{P} \subseteq...

29
Иерархия для BPP против дерандомизации

В одном предложении: подразумевает ли существование иерархии для какие-либо результаты дерандомизации?B P T I M EBPTIME\mathsf{BPTIME} но неопределенный вопрос: подразумевает ли существование иерархии для какие-либо трудные нижние границы? Влияет ли решение этой проблемы на известный барьер в...

29
Может ли вероятностная машина Тьюринга решить проблему остановки?

Компьютер с бесконечным потоком действительно случайных битов является более мощным, чем компьютер без него. Вопрос: достаточно ли он силен, чтобы решить проблему остановки? То есть может ли вероятностный компьютер определить, останавливается ли детерминированная программа? Пример вероятностного...

25
Случайный цикл самоопределения решетки внутри заданной ограничительной рамки

В связи с загадкой Slither Link мне было интересно: предположим, что у меня сетка квадратных ячеек, и я хочу найти простой цикл ребер сетки, равномерно случайным образом среди всех возможных простых циклов.n×nn×nn\times n Один из способов сделать это - использовать цепь Маркова, состояния которой...

22
Вера распространения для приблизительного реального 3LIN?

В научной статье 2002 года Мезард, Паризи и Зекчина выдвинули эвристику распространения верований для случайного 3SAT. Эксперименты показывают, что эвристика хорошо работает для соотношений ограничений на переменную, для которых вероятно существует удовлетворительное назначение. Мои вопросы: (1)...

21
От экстракторов к псевдослучайным генераторам?

Лука Тревизан показал, сколько конструкций псевдослучайных генераторов можно фактически рассматривать как конструкции экстракторов: http://www.cs.berkeley.edu/~luca/pubs/extractor-full.pdf Есть ли значимое обратное? Т.е. можно ли рассматривать «естественные» конструкции экстракторов как конструкции...

21
Сравнение экстракторов с точки зрения компромиссов между временем, случайностью и пространством?

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

21
Случайные функции низкой степени как вещественный полином

Есть ли (разумный) способ выбрать равномерно случайную булеву функцию , степень которой как вещественный полином не превосходит ?f:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\}ddd РЕДАКТИРОВАТЬ: Нисан и Сегеди показали, что функция степени зависит не более чем от координат, поэтому мы можем...

21
Оценки

Если - выпуклая функция, то неравенство Дженсена утверждает, что , и mutatis mutandis, когда вогнута. Очевидно, что в худшем случае вы не можете получить верхнюю границу в терминах для выпуклого , но есть ли граница, которая идет в этом направлении, если выпуклый, но не слишком выпуклый? Существует...

20
Проводятся ли в настоящее время исследования по внедрению экстракторов случайности?

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

20
Явная сбалансированная матрица

Можно ли построить явное 0 / 1 -матрица с N 1,5 из них таким образом, что каждый N 0,499 × N 0,499 подматрица содержит менее N 0,501 из них?N×NN×NN \times N 0/10/10/1N1.5N1.5N^{1.5}N0.499×N0.499N0.499×N0.499N^{0.499} \times N^{0.499}N0.501N0.501N^{0.501} Или, возможно, для такого свойства можно...

20
Ограниченные вероятностные распределения по глубине

Два связанных вопроса об ограниченных вычислениях глубины: 1) Предположим, что вы начинаете с n битов, и начинаться с бита i может быть 0 или 1 с некоторой вероятностью p (i) независимо. (Если это упрощает задачу, мы можем предположить, что все p (i) s равны 0,1 или 1/2.или даже то, что все они...

20
Задачи, NP-полные при рандомизированном или P / poly сокращении.

В этом вопросе мы, кажется, идентифицировали естественную проблему, которая является NP-полной при рандомизированных сокращениях, но, возможно, не при детерминированных сокращениях (хотя это зависит от того, какие недоказанные предположения в теории чисел верны). Известны ли еще такие проблемы?...

17
Рандомизировать или нет?

Этот вопрос вдохновлен Технологическим Центром Джорджии и Центром Случайности футболкой , которая спрашивает «Рандомизировать или нет ?!» Есть много примеров, когда рандомизация помогает, особенно при работе в состязательной среде. Есть также некоторые настройки, в которых рандомизация не помогает...

17
Дурачить произвольные симметричные функции

Распределение называется ϵ- обмануть функцию f, если | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . И говорят, что он обманывает класс функций, если он обманывает каждую функцию в этом классе. Известно , что & epsi -biased пространство дурака класс паритетов над подмножествами. (см....

17
Используются ли теоретически обоснованные псевдослучайные генераторы на практике?

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