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

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

polynomial-time computable collection of functions

Пусть $I$ — подмножество $\{0,1\}^*$ или $\mathbb N$, а $(f_i\,|\, i\in I)$ — семейство, в котором $f_i\in\operatorname{Fun}(X_i,\{0,1\}^*)$ ($X_i\subseteq\{0,1\}^*$) для любого $i\in I$. Тогда это семейство называется полиномиально вычислимым, если полиномиально вычислима функция $(i,x)\mapsto f_i(x)$ (при $I\subseteq\{0,1\}^*$) или функция $\left(1^i,x\right)\mapsto f_i(x)$ (при $I\subseteq\mathbb N$), где $i\in I$ и $x\in X_i$.

Пусть теперь каждому $n\in N$, где $N\subseteq\mathbb N$, поставлено в соответствие множество $D_n\subseteq\{0,1\}^*$. Тогда семейство $(f_{n,d}\,|\, n\in\mathbb N,\, d\in D_n)$, в котором $f_{n,d}\in\operatorname{Fun}(X_{n,d},\{0,1\}^*)$ ($X_{n,d}\subseteq\{0,1\}^*$) для любых $n\in N$ и $d\in D_n$, называется полиномиально вычислимым, если полиномиально вычислима функция $(1^n,d,x)\mapsto f_{n,d}(x)$, где $n\in N$, $d\in D_n$ и $x\in X_{n,d}$.

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