Список обозначений

Модель вычислений однородная

uniform model of computation

В однородной модели вычислений вычислителем является машина Тьюринга, применяемая ко входам произвольной длины. Согласно тезису Чёрча машина Тьюринга является одной из формализаций интуитивного понятия алгоритма. Поэтому мы называем вычислитель в однородной модели вычислений (т. е. машину Тьюринга) алгоритмом.

Алгоритм называется вероятностным, если он имеет доступ к оракулу RB, возвращающему независимые случайные относительно равномерного распределения вероятностей на $\{0,1\}$ биты. В случае, когда число запросов к оракулу RB при вычислении алгоритма на данном входе ограничено сверху некоторым числом $k$, вместо доступа к оракулу RB можно подать этому алгоритму на дополнительный вход строку $r\in_{\mathfrak U}\{0,1\}^k$. Если алгоритм не делает запросов к оракулу RB, то он называется детерминированным.

Алгоритм (вообще говоря, вероятностный) называется полиномиальным (или работающим за полиномиальное время), если существует полином $t$ такой, что при любых битах, полученных от оракула RB, время работы этого алгоритма на любом входе $x$ не превосходит $t(\lvert{x}\rvert)$. Аналогично формализуется понятие алгоритма с другими суперполиномиальными ограничениями на время работы.

Понятие полиномиального алгоритма можно эквивалентным образом формализовать в терминах однородных семейств булевых схем полиномиального размера в произвольном конечном полном базисе. А именно, вместо полиномиальных вероятностных машин Тьюринга можно рассматривать семейства $(C_n\,|\, n\in\mathbb N)$ булевых схем в таком базисе, удовлетворяющие следующим условиям:
  • существует полиномиальная детерминированная машина Тьюринга, которая по $1^n$ вычисляет описание схемы $C_n$ для всякого $n\in\mathbb N$ (условие однородности);
  • существует полином $p$ такой, что для любого $n\in\mathbb N$ размер схемы $C_n$ не превосходит $p(n)$;
  • при каждом $n\in\mathbb N$ схема $C_n$ имеет не менее $n$ битовых входов.
Предполагается, что на первые $n$ битовых входов схемы $C_n$ последовательно подаются биты входной строки из $\{0,1\}^n$, а на остальные битовые входы — независимые случайные относительно равномерного распределения вероятностей на $\{0,1\}$ биты.

Вероятностный алгоритм называется полиномиальным в среднем (или работающим за полиномиальное в среднем время), если существует константа $c>0$ такая, что для любого входа $x$ математическое ожидание случайной величины $T_x^c$, где $T_x$ — время работы алгоритма на входе $x$, не превосходит $\lvert{x}\rvert$. Наивный подход, при котором вероятностный алгоритм называется полиномиальным в среднем, если математическое ожидание случайной величины $T_x$ не превосходит значения некоторого полинома на $\lvert{x}\rvert$, несостоятелен хотя бы потому, что в таком случае класс полиномиальных в среднем алгоритмов не будет замкнутым относительно функциональной композиции. Существуют и другие аргументы против указанного наивного подхода.

Алгоритм $\mathcal A$ (вообще говоря, вероятностный) называется интерактивным, если он имеет (кроме других обычных лент, например, входной, выходной, рабочей) две выделенные ленты, называемые коммуникационными и обладающие следующими свойствами. Одна из этих лент (обозначим ее через $R_{\mathcal A}$) доступна только на чтение и служит для приема сообщений, а другая (обозначим ее через $S_{\mathcal A}$) доступна только на запись и служит для посылки сообщений. В любой момент вычисления алгоритм либо активен, либо находится в специальном состоянии, называемом состоянием ожидания. В период активности алгоритм производит обычные вычисления, включающие чтение с коммуникационной ленты $R_{\mathcal A}$ и запись на коммуникационную ленту $S_{\mathcal A}$. Информация, прочитанная с коммуникационной ленты $R_{\mathcal A}$ (записанная на коммуникационную ленту $S_{\mathcal A}$) в течение данного периода активности, называется сообщением, полученным (соответственно, посланным) алгоритмом в течение этого периода активности. Если же алгоритм находится в состоянии ожидания, то никакие вычисления не производятся; вывод алгоритма из этого состояния производится с помощью вспомогательной переменной другим интерактивным алгоритмом, совместно с котором производится вычисление (см. ниже).

Интерактивные алгоритмы предназначены для совместных вычислений с другими интерактивными алгоритмами. Пусть $(\mathcal A,\mathcal B)$ — пара интерактивных алгоритмов. Чтобы организовать их совместное вычисление, необходимо отождествить ленту $R_{\mathcal A}$ с лентой $S_{\mathcal B}$, а ленту $S_{\mathcal A}$ — с лентой $R_{\mathcal B}$. Изначально обе эти ленты пусты. Кроме того, алгоритмы $\mathcal A$ и $\mathcal B$ имеют общую битовую переменную $Z$ (реализуемую как лента из одной ячейки), доступную им как на чтение, так и на запись. Если $Z=0$, то в данный момент времени алгоритм $\mathcal A$ активен, а алгоритм $\mathcal B$ находится в состоянии ожидания. Если же $Z=1$, то, наоборот, в данный момент времени активен алгоритм $\mathcal B$, а алгоритм $\mathcal A$ находится в состоянии ожидания. Предположим, что инициирует вычисления алгоритм $\mathcal A$. Тогда перед началом вычисления $Z$ устанавливается в $0$, а алгоритм $\mathcal B$ — в состояние ожидания. Алгоритм $\mathcal A$ вычисляет сообщение $m_1$, записывает его на ленту $S_{\mathcal A}=R_{\mathcal B}$, присваивает переменной $Z$ значение $1$ и переходит в состояние ожидания. После этого алгоритм $\mathcal B$ выходит из состояния ожидания (сигналом к чему служит изменение значения переменой $Z$ на $1$), читает сообщение $m_1$ с ленты $R_{\mathcal B}=S_{\mathcal A}$, вычисляет сообщение $m_2$, записывает его на ленту $S_{\mathcal B}=R_{\mathcal A}$, присваивает переменной $Z$ значение $0$ и переходит в состояние ожидания. Затем алгоритм $\mathcal A$ выходит из состояния ожидания, читает сообщение $m_2$ с ленты $R_{\mathcal A}=S_{\mathcal B}$, вычисляет сообщение $m_3$, дописывает его на ленту $S_{\mathcal A}=R_{\mathcal B}$ (после сообщения $m_1$), присваивает переменной $Z$ значение $1$, переходит в состояние ожидания и т. д. Если один из алгоритмов закончил свое вычисление, то заканчивается и совместное вычисление.

Интерактивный алгоритм $\mathcal A$ называется полиномиальным (или работающим за полиномиальное время), если существует полином $t$ такой, что время работы алгоритма $\mathcal A$ при совместном вычислении с любым интерактивным алгоритмом не превосходит $t(\lvert{x}\rvert+\lvert{y}\rvert)$, где $x$ — произвольный общий вход алгоритмов, а $y$ — произвольный собственный вход алгоритма $\mathcal A$. В настоящем справочнике встречаются также интерактивные алгоритмы, полиномиальные от длины общего входа. Чтобы получить определение такого алгоритма, нужно очевидным образом модифицировать приведенное выше определение интерактивного полиномиального алгоритма. А именно, интерактивный алгоритм $\mathcal A$ называется полиномиальным от длины общего входа, если существует полином $t$ такой, что время работы алгоритма $\mathcal A$ при совместном вычислении с любым интерактивным алгоритмом и при любом собственном входе алгоритма $\mathcal A$ не превосходит $t(\lvert{x}\rvert)$, где $x$ — произвольный общий вход алгоритмов.

Отметим, что в этих определениях не участвуют сообщения, которые получает алгоритм $\mathcal A$ при совместном вычислении. В частности, не предполагается, что интерактивный полиномиальный алгоритм может прочитать полностью получаемые им сообщения. См. также [1].

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна