歸約作為下界工具（reduction as a lower-bound tool）

假設你已經知道問題 A 很難——它可證明地需要大量工作。你面對一個新問題 B，懷疑它也很難，但從頭證一個新下界很痛苦。歸約讓你借用：如果只要能快速解 B 就能快速解 A，那麼 B 至少和 A 一樣難，於是 A 的下界轉移到 B。這是證明難度的「偷懶但嚴謹」之道——你繼承它，而不是重新發明它。

以下是謹慎的邏輯，而且方向很重要。要證明 B 至少和 A 一樣難，你建一個解 A 的演算法，把 B 當副程式呼叫：取 A 的任意實例，便宜地轉換成 B 的實例，跑那個（假設存在的）快速 B 解法，再便宜地把 B 的答案轉回 A 的答案。若轉換與轉回都很便宜（比如 O(n)），那麼快速的 B 解法就會給出快速的 A 解法。但我們「知道」A 有一個下界，比如 Omega(n log n)。所以 B 也不可能解得比 Omega(n log n) 更快，否則 A 也能，與 A 的下界矛盾。符號上：一個便宜的從 A 到 B 的歸約，把 A 的下界（扣掉便宜的黏合工作）轉移到 B。經典例子：元素相異性問題歸約到排序（先排序，再掃描相鄰元素找重複），而元素相異性在代數模型中有 Omega(n log n) 下界，這是論證「類排序任務很難」的一種方式。

關於方向與所轉移之物的兩個誠實提醒。歸約有方向性：一個從 A 到 B 的歸約顯示 B 至少和 A 一樣難，「並非」A 和 B 一樣難，也不表示任一個容易。初學者老是把方向弄反，於是「證」了個寂寞。另外，黏合必須真的比你想轉移的界更便宜；若轉換輸入本身就花了 n log n，你就不能用它證 n log n 下界，因為可能是轉換本身、而非 B，在做難的工作。歸約與 NP 困難用的是同一個工具，但這裡我們定量地使用它，在某模型內把像 Omega(n log n) 這種具體的時間下界在問題之間搬移。