解開可忽略和不可忽略的定義
關於這個主題有幾個執行緒，包括：
（和別的）
但我不完全理解這些執行緒中的答案。
我的問題是：
我想看看可忽略和不可忽略的定義在直覺意義上意味著什麼，並解開定義並使用範例來查看定義如何應用。
我使用的定義是：
$ \epsilon $ 是一個函式 $ \epsilon $ : $ Z^{+} $ $ \rightarrow $ $ R^{+} $ 和
$ \epsilon $ 是非負的： $ \exists $ d: $ \epsilon $ ( $ \lambda $ ) $ \geq $ 1/ $ \lambda^{d} $ inf 經常 ( $ \epsilon $ $ \geq $ 1/多項式，對於許多 $ \lambda $ )
$ \epsilon $ 是否定的： $ \forall $ d, $ \lambda \geq \lambda_{d} $ : $ \epsilon $ ( $ \lambda $ ) $ \leq $ 1/ $ \lambda^{d} $ inf 經常 ( $ \epsilon $ $ \leq $ 1/多項式，對於大 $ \lambda $ )
幾個問題：
- 這些定義在“直覺”意義上意味著什麼？
- 做什麼 $ \epsilon $ , $ \lambda $ , d, $ \lambda^d $ 意思是？
- 你如何使用這些定義來證明 $ \epsilon $ :( $ \lambda $ )=1/ $ 2^{\lambda} $ 可以忽略不計並且 $ \epsilon $ ( $ \lambda $ )=1/ $ \lambda^{1000} $ 是不可忽略的？
（我知道其中一個範例顯示在另一個執行緒中，但我不理解他們的解決方案，我想看看定義中的每一部分在“英語”中的含義，然後看看定義如何應用於這些範例中的每一個以顯示它們是可忽略的和不可忽略的。我希望有人可以對定義提供新的解釋，並展示這些定義如何應用於這些問題和一般問題。）
謝謝！
正如評論中提到的@SEJPEM：直覺地，對於每個正多項式 $ p(n) $ ( $ n\in\mathbb{N} $ ) ，考慮函式 $ q(n)=\frac{1}{p(n)} $ , 那麼我們說函式 $ \epsilon(n) $ 如果從某個角度來看是可以忽略不計的 $ N\in\mathbb{N} $ 它遵循 $ \epsilon(n)<q(n) $ . 這意味著 $ \epsilon(n) $ 很快達到 0，因為不管你是否服用 $ p_1(n)=n $ 或者 $ p_2(n)=n^{100000} $ ，根據定義，會有 $ N_1 $ 從中 $ \epsilon(n)<\frac{1}{n} $ 和 $ N_2 $ 從中 $ \epsilon(n)<\frac{1}{n^{100000}} $ .
現在，解釋您複製的定義： $ \lambda_d\in\mathbb{N} $ 指 $ N $ 在我上面的解釋中，那麼可忽略函式的定義要求對於每個 $ \lambda\in\mathbb{N} $ 這樣 $ \lambda>\lambda_d $ （在我上面的解釋中：對於所有人 $ n $ 比這個大 $ N $ ） 它遵循 $ \epsilon(\lambda)<q_d(\lambda)=\frac{1}{p_d(\lambda)}=\lambda^d $ .
為了表明 $ \epsilon(\lambda)=\frac{1}{2^\lambda} $ 可以忽略不計，您需要證明對於每個多項式 $ p(\lambda) $ 它遵循 $ \epsilon(\lambda)=\frac{1}{2^\lambda}<q(\lambda)=\frac{1}{p(\lambda)} $ 從某個角度 $ N\in\mathbb{N} $ （這一點可能因不同的 $ p(\lambda) $ -s。現在採取一些任意 $ p(\lambda) $ ，我們可以發現這個 $ N $ 從中 $ \epsilon(\lambda)<\frac{1}{p(\lambda)} $ 如下：讓 $ p(\lambda)=\lambda^k $ 然後我們想找到 $ \lambda $ 這樣 $ \frac{1}{2^\lambda}<\frac{1}{\lambda^k} $ ，因此，我們想要找到 $ \lambda $ 這樣 $ \lambda^k<2^\lambda $ ，或者換句話說，我們想證明從一些 $ \lambda $ 期限 $ 2^\lambda $ 大於 $ \lambda^k $ ，這可以使用限制的定義來證明（參見這個證明）。
現在拿 $ \epsilon(\lambda)=\frac{1}{\lambda^{1000}} $ ，為了證明它不可忽略，你需要證明存在一些多項式 $ p(\lambda) $ 這違反了定義。取多項式 $ p(\lambda)=\lambda^{2000} $ , 不存在 $ \lambda_{2000} $ （或者 $ N $ ） 從中 $ \epsilon(\lambda)=\frac{1}{\lambda^{1000}} < q(\lambda)=\frac{1}{p(\lambda)}=\frac{1}{\lambda^{2000}} $ （即對於每個 $ \lambda\in\mathbb{N} $ 你採取，它遵循 $ \epsilon(\lambda)>\frac{1}{p(\lambda)} $ .
我希望它有所幫助。