Noticeable and Negligible Functions

Definition 1 (Negligible Function^[1]) A function  is negligible iff  such that 

A negligible function must be exponentially small (more accurately, it must be smaller than any polynomial function)

Definition 2 (Noticeable Function) A function  is noticeable iff  such that 

A noticeable function is one which is at most polynomially small.

As an example, since  is exponentially small, it is a negligible function .

On the other hand  is only polynomially small and so is noticeable. (The proof is simple - just set )

Difference between Noticeable and Non-Negligible

Definition 3 (Non-negligible Function) A function  is non-negligible iff  such that  ,

A non-negligible function is not necessarily a noticeable function. Note the key difference from a noticeable function - a non-negligible function only needs to have one  for which , whereas a noticeable function must satisfy this for any . For example, if we take any noticeable function and any negligible function and interleave them, then the resulting function will be non-negligible and non-noticeable. A concrete example is:

The function cannot be negligible, because for any odd integer, the function is only polynomially small, but it is not noticeable either, because for any even integer, it is exponentially small.

Sum of Negligible Functions

The sum of two negligible functions  and  is still negligible. Intuitively, even if you add two functions that are exponentially small, that cannot give a function that is polynomially small, and so the sum is still negligible.

Theorem 1: If  and  are two negligible functions, then their sum is also negligible.

: We need to show that for any  we can find  such that  So, consider an arbitrary . 

Then, since  and since  and  are negligible, there exists and  such that:  and  

Choose . Then, for any , we have  since  Thus  and  is negligible. 

参考资料