什麼是不可忽略的功能？
我簡要地看了一下Bellare 和 Goldreich 的“知識證明的定義”，我對他們的定義有點困惑。
我的印像是一個微不足道的功能 $ f $ 被定義為類似 $$ \forall\ polynomials\ p\ \exists k\ s.t.\ \forall x > k: f(x) < \frac{1}{p(x)} $$
而那個不可忽略的只是意味著它不可忽略。然而，該論文指出：“換句話說，可忽略不是對不可忽略的否定！” （第 5 頁）這似乎是基於“一個不可忽略的函式在 $ n $ 是一個函式，它從下面漸近地由以下形式的函式界定 $ n^{-c} $ 對於一些常數 $ c $ ”（第 4 頁），我將其翻譯為 $$ \exists\ polynomial\ p\ and\ k\ s.t.\ \forall x > k: f(x) > \frac{1}{p(x)} $$ 不同之處在於功能以某種方式交替。
這是一個有點奇怪的問題，因為數學似乎很清楚，但我對常見的用法感到困惑。這是一般重要的事情嗎？我從未見過其他地方討論過它。
- **可忽略的函式：**函式 $ \mu $ 可以忽略不計 $ \forall c \in N ;; \exists n_0 \in N $ 這樣 $ \forall n \geq n_0, \mu(n) < n^{−c}. $
正如我們現在一般，一個可忽略的函式比任何多項式都小。我們還有一個等效的極限定義；
$ f(n) $ 比每個多項式都可以忽略不計 $ q(n) $ 我們有;
$$ \lim_{n \rightarrow \infty} q(n) f(n) =0 $$
簡單的例子是 $ 2^{-n},2^{-\sqrt{n}}, \text{ and } n^{- \log n} $ .
- **不可忽略的函式：*一個函式 $ \mu(n) $ 不可忽略當且僅當 $ \exists c \in N $ 這樣 $ \forall n_0 \in N, \exists n \geq n_0 $ 這樣 $ \mu(n) \geq n^{-c}. $
為了不可忽略，只有一名候選人足以證明 $ n \geq n_0 $ 為此 $ \mu(n) \geq n^{-c} $ .
- **值得注意的功能：**一個功能 $ \mu $ 是明顯的當且 $ \exists c \in N, n_0 \in N $ 這樣 $ \forall n \geq n_0, \mu(n) \geq n^{-c}. $
正如我們所看到的，與不可忽略的區別是；對所有人 $ n \geq n_0 $
一個例子是 $ n^{-3} $ 這只是多項式緩慢（就像任何多項式一樣）
弱單向函式是在顯著函式上定義的。
交織是生成區分範例的關鍵。取任何明顯且可忽略的函式並將它們交錯；
$$ \mu(n) = \cases{ 2^{-n} & : $x$ is even \ n^{-3} & : $x$ is odd} $$
$ \mu $ 是一個不可忽略且不顯眼的功能！。
*量詞否定：在否定中 $ \neg\forall = \exists $ 和 $ \neg \exists = \forall $