1

I'm studying about complexity and reaching negligible. Can anyone tell me if $f(x)$ is a negligible function and $p(x) \in \mathbb{R}$ then $p(x) . f(x)$ is a negligible function?

Minh. Pham
  • 59
  • 2
  • 1
    What is your definition of "negligible function"? – Math1000 Jan 06 '20 at 04:24
  • Those kinds of questions are the basics of the negligible function. You can easily prove/disprove this by using your definition. – kelalaka Jan 06 '20 at 08:05
  • A function $f: \mathbb{N} \to \mathbb{R}$ is called negligible if with every $p(x) \in \mathbb{R}[x]$, there exist $K \in \mathbb{N}$ such that with every $k > K$ an $p(k) \neq 0$ we have $$f(k) < \dfrac{1}{|p(k)|}$$ – Minh. Pham Jan 07 '20 at 03:14

1 Answers1

0

Let $f'(x) = f(x) \cdot p(x)$

  1. f(x) is negligible means that it is smaller than the inverse of any polynomial, for all sufficiently large n. In your case, given any polynomial $q(x)$, it is smaller than $1/p(x)q(x)$

  2. By using the limit definition of negligibility.

    $f(x)$ is negligible than for every polynomial $q(x)$ we have;

    $$\lim_{x \rightarrow \infty} q(x) f(x) =0$$

    We need to show that for every $q(x)$, $f'(x)$ is negligible;

    $$\lim_{n \rightarrow \infty} q(x) f'(x) = \lim_{x \rightarrow \infty} q(x) [p(x) f(x)] =0$$

    This is true; since $f(x)$ is negligible implies for any polynomial;

    $$\lim_{n \rightarrow \infty} [q(x) p(x)] f(x) =0,$$ where $q(x) p(x)$ is a polynomial.

kelalaka
  • 1,637