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

12

Пусть будет константой. Как мы можем с уверенностью построить псевдослучайный генератор, который обманывает конечные автоматы d- состояния?dd

Здесь, -state имеет конечные автоматы d узлов, начальный узел, набор узлов , представляющие принимают состояния, и две направленных ребер помечены 0, 1 , выходят из каждого узла. Он изменяет состояние естественным образом, так как читает входные данные. Для заданного find найдите f : { 0 , 1 } k{ 0 , 1 } n такое, что для любого конечного автомата d-состояния, вычисляющего некоторую функцию A ,ddϵf:{0,1}k{0,1}ndA

|PxUk(A(f(x))=1)PxUn(A(x)=1)|<ϵ.

Здесь обозначает равномерное распределение по k переменным, и мы хотим, чтобы k было как можно меньше (например, log n ). Я думаю о том, что d порядка n , хотя мы также можем задать вопрос более широко (например, увеличится ли число требуемых битов с n ?).Ukkklogndnn

Некоторый фон

Построение псевдослучайных генераторов важно для дерандомизации, но общая проблема (PRG для алгоритмов полиномиального времени) до сих пор оказалась слишком сложной. Тем не менее, был достигнут прогресс в PRG для расчета в ограниченном пространстве. Например, эта недавняя статья ( http://homes.cs.washington.edu/~anuprao/pubs/spaceFeb27.pdf ) дает оценку приблизительно для обычных программ разветвления с однократным чтением. Вопрос с общими одноразовыми ветвящимися программами остается открытым (с k = log n ), поэтому мне интересно, известен ли ответ на это упрощение. (Конечный автомат похож на разветвляющуюся программу с однократным чтением, где все слои одинаковы.)lognlogdk=logn

Холден Ли
источник
это могло бы помочь детализировать / описать некоторых, почему это естественная формулировка проблемы, то есть происхождение / bkg / details / обоснование выражения вероятности. Есть ли другие известные решения вопроса для других моделей? это связано со структурой PAC и т. д.?
vzn
Я добавил немного фона.
Холден Ли
может быть, идея наборов дурака FSM (p12) будет хорошо работать здесь? («Если L имеет бесконечное множество дураков, то L не принимается никаким DFA.»)
vzn

Ответы:

1

Mn

это, по-видимому, то же самое доказательство также приводит RJlipton в своем блоге «Гарантия на генератор Nisans» . доказательство, по-видимому, исходит из статьи. Насколько силен псевдослучайный генератор Нисана? Давид, Папаконстантину, Сидиропулос (2010). также обратите внимание на более глубокий вопрос, и лучшие оценки связаны с разделением классов по сложности:

LNP

ВЗН
источник
обратите внимание, далее посмотрите, статья DPS является продолжением статьи Nisans [NIS92] в их ссылках на ограниченные в пространстве машины с несколькими проходами. эта ссылка - Н. Нисан. Псевдослучайные генераторы для ограниченных в пространстве вычислений. Combinatorica, 12 (4): 449–461, 1992. (также STOC'90).
vzn
1
Возможно, если вы прочитаете статью Нисана, вы заметите, что он излагает свою теорему в терминах автоматов. Также было бы неплохо, если бы вы дали некоторые количественные оценки
Сашо Николов
Обратите внимание, что некоторые утверждения thm относятся к терминам logspace. Смотрите также дезориентация пространства-ограниченные модели и низкие полиномы степени опроса , Ли Ян, вторы 1,3 p6 Обойти один раз читающего журнала пространство машины Тьюринга
ВЗН
И этот вопрос, и оригинальная статья дают представление о ФШМ. Так что ваш комментарий вряд ли актуален.
Сашо Николов
2
Вы можете просто сформулировать соответствующую теорему в формулировке FSM из статьи Нисана в своем ответе? Не заметки, которые утверждают это по-другому, а не обзорный документ, в котором говорится это по-другому: сначала сформулируйте фактический ответ на фактический вопрос ? Есть ли что-то сложное для понимания, почему это хорошо?
Сашо Николов