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

Функция существенная

noticeable function

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

Это определение легко переформулировать для функций, определенных на бесконечных подмножествах $\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)\geqslant1/p(n)$ выполняется при всех достаточно больших $n\in N$. В этом случае также говорят, что величина $\xi(n)$ существенна как функция от $n\in N$.

Отметим, что всякая существенная функция вышеуказанного вида не является пренебрежимо малой, но обратное неверно.

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