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

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

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

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

$|\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\neq 0\\{\frac {1}{x^{1000}}},&x\mod 2=0\end{cases}}$ — не нехтовна.