問題的下界（lower bound on a problem）

假設你發明了一個聰明的排序方法，跑出 O(n log n) 的時間。自然會接著問：有沒有人、用什麼辦法，能做得更好——在 O(n) 時間內排好？下界是對整個「問題」的承諾，而不是對你那個特定方法的承諾：它說在某套規則之下，每一個正確的演算法在最壞情況下都至少得做這麼多工作。它是釘在難度本身底下的一塊地板。

要小心區分兩種非常不同的陳述。某一個演算法的執行時間是問題的上界：它證明這個問題最多花那麼多時間就能解。下界則是相反方向的主張，而且通常難證得多，因為你不能只拿出一個演算法——你得一次論證所有可能的演算法，包括還沒人想到的那些。讓這種論證可行的標準辦法，是固定一個計算模型（例如比較模型），然後計算在該模型中、最理想演算法的最省一次執行所需的工作量。當下界（地板）與上界（已知最佳演算法）相遇時，例如比較排序的 Omega(n log n) 與 O(n log n)，我們就說這個問題的複雜度已塵埃落定，記作 Theta(n log n)。

兩個誠實的提醒。第一，下界永遠相對於某個模型：排序的 Omega(n log n) 下界在比較模型中成立，但基數排序（radix sort）靠「不比較」鍵值來打敗它——它讀鍵值的位數，那是不同的模型，所以並未違反此界。第二，問題的下界是最壞情況的陳述：它說「某些」輸入會逼出這麼多工作，而不是「每個」輸入都如此。證明好的下界是計算機科學中最深刻的活動之一；對許多問題，包括所有與 P 對 NP 相關的問題，目前完全不知道有任何強下界。