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

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

non-uniform model of computation

В неоднородной модели вычислений вычислителем является семейство $(\mathcal A_n\,|\, n\in\mathbb N)$ машин Тьюринга (называемых в настоящем справочнике алгоритмами); при этом предполагается, что алгоритм $\mathcal A_n$ применяется к входам длины $n$ ($n\in\mathbb N$). Эквивалентным образом вычислителем в неоднородной модели вычислений можно считать пару $(\mathcal A,a)$, где $\mathcal A$ — алгоритм с двумя входами и $a$ — семейство $(a_n\,|\, n\in\mathbb N)$ строк из $\{0,1\}^*$. В этом случае результатом вычисления на входе $x\in\{0,1\}^*$ будет $\mathcal A\left(x,a_{\lvert{x}\rvert}\right)$.

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

Если на определенный выше вычислитель не накладывать никаких дополнительных ограничений, то в неоднородной модели будут вычислимы все функции из произвольного подмножества $\{0,1\}^*$ в $\{0,1\}^*$. Поэтому рассмотрение неоднородной модели вычислений имеет смысл лишь при некоторых таких ограничениях.

Определение 1 полиномиальный вычислитель в неоднородной модели вычислений
Семейство алгоритмов $(\mathcal A_n\,|\, n\in\mathbb N)$ (или пара $(\mathcal A,(a_n\,|\, n\in\mathbb N))$ во втором варианте определения) называется полиномиальным (или работающим за полиномиальное время) вычислителем в неоднородной модели вычислений, если
  1. существует полином $p$ такой, что для любого $n\in\mathbb N$ длина описания алгоритма $\mathcal A_n$ (или длина строки $a_n$ во втором варианте определения) не превосходит $p(n)$;
  2. существует полином $t$ такой, что для любых $n\in\mathbb N$ и $x\in\{0,1\}^n$ время работы алгоритма $\mathcal A_n$ на входе $x$ (или алгоритма $\mathcal A$ на входе $(x,a_n)$ во втором варианте определения) не превосходит $t(n)$.
Аналогично формализуется понятие вычислителя с другими суперполиномиальными ограничениями на время работы.

Вообще говоря, алгоритмы $\mathcal A_n$ (или алгоритм $\mathcal A$ во втором варианте определения) могут быть вероятностными. В этом случае соответствующий вычислитель естественно назвать вероятностным. Однако во многих важных случаях в неоднородной модели вычислений достаточно ограничиться рассмотрением детерминированных вычислителей, т. е. таких, что алгоритмы $\mathcal A_n$ (или алгоритм $\mathcal A$ во втором варианте определения) детерминированы. Приведем два замечания, подтверждающие этот тезис.

Замечание 2 см. также [1]
Предположим, что для каждого $n\in\mathbb N$ определено распределение вероятностей $\mathfrak X_n$ на множестве $\{0,1\}^n$. Пусть также каждому $x\in\{0,1\}^*$ поставлено в соответствие множество $M_x\subseteq\{0,1\}^*$. Рассмотрим следующую задачу: по $x\leftarrow\mathfrak X_n$ найти какой либо элемент множества $M_x$ ($n\in\mathbb N$). Тогда для любого полиномиального вероятностного вычислителя $(\mathcal A_n\,|\, n\in\mathbb N)$ в неоднородной модели вычислений существует полиномиальный детерминированный вычислитель $(\mathcal B_n\,|\, n\in\mathbb N)$ в этой модели, решающий эту задачу с не меньшей вероятностью, чем исходный, т. е. \[ \Pr(\mathcal B_n(x)\in M_x)\geqslant\Pr(\mathcal A_n(x)\in M_x) \] для любого $n\in\mathbb N$, где $x\leftarrow\mathfrak X_n$. А именно, выберем какой либо полином $p$ такой, что при каждом $n\in\mathbb N$ алгоритм $\mathcal A_n$ при вычислении на произвольном входе $x\in\{0,1\}^n$ использует не более $p(n)\in\mathbb N$ случайных битов. Тогда в качестве $\mathcal B_n$ можно взять $\mathcal A_n(\cdot;r_n)$, где $r_n$ — бинарная строка, на которой достигается максимум $\Pr_{x\leftarrow\mathfrak X_n}(\mathcal A_n(x;r)\in M_x)$ по $r\in\{0,1\}^{p(n)}$ ($n\in\mathbb N$).
Замечание 3
Пусть функция $\pi\colon\{0,1\}^*\to\{0,1\}$ вычислима некоторым полиномиальным вероятностным вычислителем $(\mathcal A_n\,|\, n\in\mathbb N)$ в неоднородной модели вычислений с вероятностью не менее $1/2+1/p(\lvert{x}\rvert)$ (где $p$ — некоторый полином, а $x$ — аргумент функции $\pi$), т. е. \[ \Pr\left(\mathcal A_{\lvert{x}\rvert}(x)=\pi(x)\right)\geqslant\frac12+\frac1{p(\lvert{x}\rvert)} \] для любого $x\in\{0,1\}^*$. Тогда аналогично известному доказательству включения $\mathrm{BPP}\subseteq\mathrm{P/poly}$ (см., например, [2], [1], [3] [4]) легко показать, что существует полиномиальный детерминированный вычислитель $(\mathcal B_n\,|\, n\in\mathbb N)$ в неоднородной модели вычислений, для которого $\mathcal B_{\lvert{x}\rvert}(x)=\pi(x)$ при всех $x\in\{0,1\}^*$.
Эквивалентным образом полиномиальным детерминированным вычислителем в неоднородной модели вычислений можно считать семейство $(C_n\,|\, n\in\mathbb N)$ булевых схем в произвольном конечном полном базисе, удовлетворяющее следующим условиям:
  • существует полином $p$ такой, что для любого $n\in\mathbb N$ размер схемы $C_n$ не превосходит $p(n)$;
  • при каждом $n\in\mathbb N$ схема $C_n$ имеет $n$ битовых входов.
При этом предполагается, что схема $C_n$ применяется к входам длины $n$ ($n\in\mathbb N$).

Следующее замечание показывает, что неоднородная модель вычислений сильнее однородной.

Замечание 4 см. [2], [3]
Пусть $S$ — произвольное нерекурсивное подмножество $\mathbb N$. Тогда очевидно, что язык $\bigcup_{n\in S}\{0,1\}^n$ в неоднородной модели вычислений распознаваем даже семейством булевых схем, каждая из которых всегда возвращает либо $0$, либо $1$. В то же время в однородной модели вычислений этот язык не распознаваем никаким алгоритмом.

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [2] Китаев, А. and Шень, А. and Вялый, М. «Классические и квантовые вычисления» 1999
  • [3] Goldreich, O. «Computational complexity: A conceptual perspective» 2008
  • [4] Luby, M. «Pseudorandomness and cryptographic applications» 1996

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