3
$\begingroup$

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

question

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?

Improve this question
$\endgroup$
1
  • 1
    $\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
    Commented Apr 16, 2018 at 9:11

2 Answers 2

Reset to default
3
$\begingroup$

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$...
Improve this answer
$\endgroup$
0
$\begingroup$

I'll try to solve this and I'll be happy if someone would be able to say it's correct or not.

Let p be a positive polynomial. Since $negl_1$ is negligible there's a number N such that for any n>N we have: $$negl_1(n) < \frac{1}{p(n) * p(n)}$$

(as polynomial * polynomial is polynomial)

This gives us that for any n>N we have:

$$negl_2(n) = p(n) * negl_1(n) < p(n) * \frac{1}{p(n) * p(n)} = \frac{1}{p(n)}$$

And we got that $negl_2$ is a negligible function as well.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Welcome to Cryptography.Se We have $\LaTeX$/ mathJax enabled in our site. $\endgroup$
    – kelalaka
    Commented Jan 10 at 16:22
  • $\begingroup$ Thanks, edited :) $\endgroup$
    – GMathWagon
    Commented Jan 10 at 17:52
  • 1
    $\begingroup$ You cannot assume a factorization of the type $p(n) p(n)$ or even $p(n) p'(n)$ with nonconstant polynomials on the right hand side of your first equation. $\endgroup$
    – kodlu
    Commented Jan 10 at 20:27
  • 1
    $\begingroup$ It's not a factorization, it's a new polynomial made of multiplication of two polynomial $\endgroup$
    – GMathWagon
    Commented Jan 10 at 22:27
  • $\begingroup$ all you can assume when a function is negligible is that there is some nonconstant growing polynomial, not that there is a polynomial growing fast enough that it is growing faster than the product of two nonconstant polynomial. so you are assuming what you want to prove $\endgroup$
    – kodlu
    Commented Jan 11 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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