302
смотрим два распределения X и Y по строкам некоторой длины A; то есть, каждый
X и Y присваивает некую вероятность каждой строке {0, 1}A. Говоря, что некоторый
алгоритм D не может отличить эти два распределения, мы имеем в виду, что D не
может сообщить, является ли данная строка отобранной в соответствии с распределе-
нием X или является ли данная строка отобранной в соответствии с распределением
Y . Иными словами, если представить D, выводящий «0», когда считается, что его
входные данные были отобраны в соответствии с X и выводящий «1», если предпола-
гается, что его входные данные были отобраны в соответствии с Y , тогда вероятность
того, что D выводит «1» должна быть приблизительно той же,
независимо от того,
откуда D обеспечен образцом – из X или из Y . Другими словами, мы
хотим, чтобы
было малым.
Это должно напоминать способ, которым мы определили псевдослучайные
генераторы и, действительно, скоро мы формально заново определим понятие
псевдослучайного генератора, используя данную терминологию.
Формальное определение вычислительной неразличимости относится к вероят-
ностным ансамблям, которые представляют собой бесконечные последовательности
распределений вероятности. (Этот формализм необходим для осмысленного асим-
птотического подхода). Хотя это понятие можно обобщить, мы рассматриваем веро-
ятностные ансамбли, в которых основные распределения индексированы натураль-
ными числами. Если для каждого натурального числа n существует распределение
Xn, то X = {Xn}n∈N является вероятностным ансамблем. Часто бывает так, что Xn
= Yt(n) для некоторой функции t, в этом случае мы записываем {Yt(n)}n∈N
вместо
{Xn}n∈N.
Нас интересуют только «эффективно отбираемые» вероятностные ансамбли.
Ансамбль X = {Xn}n∈N является эффективно отбираемым, если существует
вероятностный полиномиально-временной алгоритм S , такой что случайные
переменные S(1n) и Xn распределены идентично. То есть, алгоритм S является
эффективным способом выбора X . Теперь можно формально определить, что
означает для двух ансамблей, быть вычислительно неразличимыми.
Достарыңызбен бөлісу: