ฟังก์ชันที่ไม่ละเลยคืออะไร

• ฟังก์ชั่นเล็กน้อย: ฟังก์ชั่น $\mu$ เป็น เล็กน้อย ถ้า $\forall c \in N \;\; \มีอยู่ n_0 \ใน 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{ และ } n^{- \log n}$.

• ฟังก์ชั่นที่ไม่สำคัญ:^* ฟังก์ชั่น $\mu(n)$ เป็น ไม่ละเลย ถ้า $\exists c \ใน N$ ดังนั้น $\forall n_0 \ใน N, \มีอยู่ n \geq n_0$ ดังนั้น $\mu(n) \geq n^{-c}.$

  ผู้สมัครเพียงคนเดียวก็เพียงพอที่จะแสดงสิ่งนั้น $n \geq n_0$ ซึ่ง $\mu(n) \geq n^{-c}$.

• ฟังก์ชั่นที่สังเกตได้: ฟังก์ชั่น $\mu$ เป็น สังเกตได้ ถ้า $\มีอยู่ c \ใน N, n_0 \ใน N$ ดังนั้น $\forall n \geq n_0, \mu(n) \geq n^{-c}.$

  ดังที่เราเห็นความแตกต่างจากการไม่ละเลยคือ สำหรับทุกอย่าง $n \geq n_0$

  ตัวอย่างคือ $n^{-3}$ ซึ่งเป็นพหุนามช้าเท่านั้น (เช่นพหุนามใด ๆ )

  ฟังก์ชันทางเดียวที่อ่อนแอถูกกำหนดไว้ในฟังก์ชันที่สังเกตได้

การแทรกสลับเป็นกุญแจสำคัญในการสร้างตัวอย่างที่แตกต่าง นำฟังก์ชั่นที่เห็นได้ชัดเจนและไม่สำคัญและแทรกเข้าไป;

$$\mu(n) = \cases{ 2^{-n} & : $x$ เป็นเลขคู่ \ n^{-3} & : $x$ เป็นเลขคี่}$$

$\mu$ เป็นฟังก์ชันที่ไม่ละเลยและไม่สังเกตเห็นได้!.

_{^*การปฏิเสธเชิงปริมาณ: ในคำปฏิเสธ $\neg\forall = \exists$ และ $\neg \exists = \forall$}