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

Функция пренебрежимо малая

negligible function

Функция $\nu\colon X\to\{r\in\mathbb R\,|\, r\geqslant0\}$, где $X$ — бесконечное подмножество $\{0,1\}^*$, называется пренебрежимо малой, если для любого полинома $p$ неравенство $\nu(x)\leqslant1/p(\lvert{x}\rvert)$ выполняется при всех $x\in X$ достаточно большой длины. В этом случае также говорят, что величина $\nu(x)$ пренебрежимо мала как функция от $x\in X$. Говоря неформально, функция $\nu$ пренебрежимо мала, если она убывает быстрее, чем $x\mapsto1/p(\lvert{x}\rvert)$ для любого полинома $p$.

Это определение легко переформулировать для функций, определенных на бесконечных подмножествах $\mathbb N$. А именно, функция $\xi\colon N\to\{r\in\mathbb R\,|\, r\geqslant0\}$, где $N$ — бесконечное подмножество $\mathbb N$, называется пренебрежимо малой, если функция $1^n\mapsto\xi(n)$ ($n\in N$) пренебрежимо мала в смысле вышеуказанного определения, т. е. если для любого полинома $p$ неравенство $\xi(n)\leqslant1/p(n)$ выполняется при всех достаточно больших $n\in N$. В этом случае также говорят, что величина $\xi(n)$ пренебрежимо мала как функция от $n\in N$. Говоря неформально, функция $\xi$ пренебрежимо мала, если она убывает быстрее, чем $1/p$ для любого полинома $p$.

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