Нехтовна функція

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Нехтовна функція (англ. negligible function) — функція \mu(x):\mathbb{N}{\rightarrow}\mathbb{R} така, що для кожного додатнього цілого c існує ціле Nc таке, що для всіх x > Nc,

|\mu(x)|<\frac{1}{x^c}.

Тотожно, ми можемо використовувати таке визначення: Функція \mu(x):\mathbb{N}{\rightarrow}\mathbb{R} є нехтовною, якщо для кожного додатнього багаточлену poly(·) існує ціле Npoly > 0 такий, що для всіх x > Npoly

|\mu(x)|<\frac{1}{\text{poly}(x)}.

Приклади[ред.ред. код]

|\mu(x)|<\frac{1}{2^x} — нехтовна,
|\mu(x)|<\frac{1}{x^{1000}} — не нехтовна, бо якщо покласти с = 10 000, тоді \frac{1}{x^{1000}}>\frac{1}{x^c},
f(x) = \begin{cases}\frac{1}{2^x}, &  x\mod 2 \ne 0\\ \frac{1}{x^{1000}}, &  x\mod 2 = 0\end{cases} — не нехтовна.