My question is about proving that a function is negligible if it is ran polynomial number of times.


This my solution: By the definition of negligibility, we have $negl_1(n) < 1/p'(n)$ where $p'(n)$ is any polynomial. We multiply $p(n)$ both sides: $p(n)*negl_1(n) < p(n)/p'(n)$.

We let $p'(n)>>p(n)$. There is always a $p'(n)$ that satisfies this inequality. Thus, $negl_2(n) = p(n)*negl_1(n)$ is negligible.

Is my solution correct?

  • $\begingroup$ You showed that there exists some polynomial function p', instead what you're looking for is to show that for any polynomial function p', then negl is smaller $\endgroup$ – Florian Bourse Apr 16 '18 at 9:11

Your solution is not correct. You have to show that $\mathbf{\text{negl}_2}$ satisfies the definition of negligible functions and what you "showed" actually is that given any sufficiently large polynomial $p'(n)$, it holds that $\mathbf{\text{negl}_2} < \frac{p(n)}{p'(n)}$.

I see two easy ways of solving that exercise:

  • Try to prove it by contradiction supposing that $\mathbf{\text{negl}_2}$ is not negligible and then finding a polynomial whose inverse is asymptotically smaller than $\mathbf{\text{negl}_1}$.
  • Try to prove it directly: from any given polynomial $p'(n)$, you know that $p(n)p'(n)$ is a polynomial, therefore, $\mathbf{\text{negl}_1}$ must be smaller than $1 / (p(n)p'(n))$ for all $n$ bigger than some $n_0$...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.