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

Нехтовна функція (англ. 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 \ne 0\\ \frac{1}{x^{1000}}, & x\mod 2 = 0\end{cases}$ — не нехтовна.