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

Функция трудно аппроксимируемая

hard to approximate function
Определение 1 трудно аппроксимируемая функция; см. также [1]
Пусть $f$ — функция из $\{0,1\}^*$ в $\{0,1\}^*$. Пусть также $h\colon\{0,1\}^*\to\{0,1\}^*$ — функция, отображающая $\{0,1\}^n$ в $\{0,1\}^{m(n)}$ при любом $n\in\mathbb N$. Тогда функция $h$ называется трудно аппроксимируемой по функции $f$, если для любого полиномиального вероятностного алгоритма $\mathcal A$ и для любого полинома $p$ неравенство \[ \Pr(\mathcal A(1^n,f(\widetilde u_n))=h(\widetilde u_n))\leqslant\frac1{2^{m(n)}}+\frac1{p(n)} \] выполняется при всех достаточно больших $n\in\mathbb N$. Другими словам, функция $h$ трудно аппроксимируема по функции $f$, если для любого полиномиального вероятностного алгоритма $\mathcal A$ величина $\max\left(0,\Pr(\mathcal A(1^n,f(\widetilde u_n))=h(\widetilde u_n))-2^{-m(n)}\right)$ пренебрежимо мала как функция от $n\in\mathbb N$.

Понятие функции, трудно аппроксимируемой по функции $f$, является формализацией понятия функции, значение которой на элементе $x$ трудно вычислить по $f(x)$. Следующее предложение указывает на тесную связь понятий трудно аппроксимируемой и трудной функции.

Предложение 2 [1]
Пусть $f$ — функция из $\{0,1\}^*$ в $\{0,1\}^*$, а $h\colon\{0,1\}^*\to\{0,1\}^*$ — функция, отображающая $\{0,1\}^n$ в $\{0,1\}^{m(n)}$ при любом $n\in\mathbb N$. Тогда если $h$ трудна для $f$, то $h$ полиномиально вычислима и трудно аппроксимируема по $f$. Наоборот, если $m(n)=O(\log n)$ при $n\in\mathbb N\setminus\{0\}$, $h$ полиномиально вычислима и трудно аппроксимируема по $f$, то $h$ трудна для $f$. Таким образом, если $m(n)=O(\log n)$ при $n\in\mathbb N\setminus\{0\}$, то $h$ трудна для $f$ тогда и только тогда, когда $h$ полиномиально вычислима и трудно аппроксимируема по $f$.

Литература

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

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