用歸約建立下界

本階把我們帶到了哪裡

你現在已見過三種方式來證明某個問題「無法」比某個門檻更快被解開——即無論多聰明的演算法都贏不了它。第一篇釘住了下界究竟在主張什麼：那是關於某個模型裡「每一個」可能演算法的陳述，而非關於某一支程式。決策樹模型給了那個主張一個形狀：任何以比較為基礎的方法都是一棵「是／否」問題的樹，而一棵有 L 個可達葉子的樹至少需要 log2(L) 的深度。從那裡，比較排序的 Omega(n log n) 下界幾乎免費地掉了出來，因為排序必須區分全部 n! 種排列，而 log2(n!) 是 Theta(n log n)。接著對手論證給了第二種、親手操作的技術：一個對手回答你的查詢，盡量讓越多可能結果存活，逼你問許多問題。

那兩者都是「直接」進攻：你盯著問題本身，數它非做不可的事。這最後一篇給你第四種工具，它在精神上截然不同、往往遠更好使——歸約。其想法是去「借」一個你已經信任的下界。若快速解開問題 B 能讓你快速解開問題 A，而你已知 A 很難，那麼 B 也必定很難——否則你就能藉由繞道 B 而得到一個快速的 A。你完全不必對 B 的內部難度推理。你只是把它接管到一個難度已成定局的問題上。這種「借」，正是讓歸約成為整個演算法與複雜度領域裡硬度結果之主力的原因。

一個下界歸約的形狀

讓我們把邏輯做到滴水不漏，因為歸約以「不小心被弄反」而聞名。一個從 A 到 B 的歸約是一份食譜：把 A 的任意實例轉成 B 的一個實例、執行一個（假想的）B 的求解器、再把 B 的答案翻譯回 A 的答案。若這兩個翻譯步驟相對於我們追求的界限都很便宜，那麼任何 B 的求解器都給了我們一個速度本質上相同的 A 的求解器。把那句話讀兩遍：一個「從 A 到 B 的」歸約說明的是 B 至少和 A 一樣難，而非反過來。我們把「難」的問題 A 推過 B，以證明 B 繼承了 A 的難度。初學者老是把它弄反；讓箭頭從已知為難的問題指向你想定罪的那個問題。

從一個已知為難的問題 A 開始，它的下界你已信任（這裡是排序的 Omega(n log n)）。
把 A 的任意實例映射成 B 的一個實例，只用便宜的工作——這裡至多 O(n)。
想像一個快速的 B 求解器在那個實例上執行並回傳它的答案。
把 B 的輸出翻譯回 A 所要求的答案，同樣便宜地（至多 O(n)）。
下結論：快速的 B 會產出快速的 A；既然 A 無法超越它的界限加速，B 便繼承了那個界限。

經典之例：元素相異其實是排序的化裝

這是本主題裡最乾淨的歸約。元素相異問：給 n 個數，它們是否兩兩不同，還是有某個值重複？它感覺比排序容易——我們只要一個是／否，而非完整的排列。然而在比較模型裡它也花 Omega(n log n)，而歸約用一句話就證明了。假設有人遞給你一個魔法盒子，它能用 o(n log n) 次比較判定相異性。我們會用它來排序，而排序在 n log n 以下是不可能的，所以那個盒子不可能存在。

但等等——一個相異盒子只輸出「是」或「否」；那怎麼可能拿來排序？這是微妙而美麗的部分，也是為何元素相異是教科書的範例。這個歸約「並非」直接繞道比較排序問題。它繞道一個「幾何」上的表親，而那個表親的下界本身是用代數決策樹論證證明的：n 維空間中「全相異」區域的連通分量數目是 n!，而一棵分開這麼多分量的代數決策樹需要 Omega(n log n) 的深度。本篇誠實的收穫是那個論證的「形式」——一層便宜的包裝加上一個借來的下界——即使這裡借來的下界源於代數決策樹模型而非排序本身。許多書把這條鏈鬆散地說成「相異和排序一樣難」；精確版本是把 n! 經由幾何繞過去。

把界限再傳下去：凸包與它的朋友們

一旦你擁有一個 n log n 下界，歸約就讓你把它在幾何裡到處加盟。考慮凸包：給平面上 n 個點，找出包含它們全部的最小凸多邊形，並把它的頂點沿邊界依序列出。凸包下界是 Omega(n log n)，而「從排序來」的歸約令人愉悅地直觀。取你想排序的 n 個數 x_1, ..., x_n。把每個抬到拋物線 y = x^2 上，產生點 (x_i, x_i^2)。每個這樣的點都是凸包的頂點，因為拋物線是凸的——沒有一個點落在其他點構成的內部。所以一個凸包演算法必須回傳全部 n 個點，且它「沿邊界依序」回傳，而沿拋物線底部那正好是排序後的順序。讀出 x 座標，你就把那些數排好了。

to sort  x_1 .. x_n :
    map each x_i  ->  point ( x_i , x_i^2 )    # O(n), lift onto parabola
    H = ConvexHull( points )                   # all n points are hull vertices
    read x-coords of H in boundary order       # O(n), this is sorted order
# a sub-(n log n) hull  =>  sub-(n log n) sort  =>  impossible

排序到凸包的歸約：兩端各一層線性包裝，把凸包下界頂到 Omega(n log n)。

兩個包裝步驟——抬到拋物線上、以及讀出來——顯然都是 O(n)。所以一個以 o(n log n) 執行的凸包演算法會產出一個 o(n log n) 的排序，而那我們已證明不可能。因此凸包需要 Omega(n log n)，且這個界限是「緊」的：Graham 掃描及其他演算法達到 O(n log n)，於是我們把地板對上了真正的天花板。同樣的拋物線把戲、或其近親，把 n log n 下界轉移到最近點對、以及計算半平面的交集——計算幾何的一整片鄰里，透過一行的歸約，從排序繼承了它的難度。

為何歸約是通往複雜度其餘部分的橋

上面這一切都用歸約在比較式模型裡的具體問題之間搬動一個「精確」的 Omega(n log n) 下界。但同樣的這個邏輯動作放大後，正是現存最著名硬度理論的引擎。一個從 A 到 B 的多項式時間歸約說：在多項式時間內把任意 A 實例轉成一個 B 實例，使得一個多項式時間的 B 求解器給出一個多項式時間的 A 求解器。這在精神上與我們的拋物線把戲一模一樣——只是現在「便宜」指的是「多項式」而非「線性」，而「難」指的是「沒有已知的多項式演算法」而非「在 n log n 以下」。這就是單一顆硬度種子如何一次散播到上千個問題。

然而這裡住著整個主題最深的一份誠實。我們證明的 n log n 下界是「無條件」的——它們在其模型內絕對成立、不附帶任何假設，因為決策樹的計數滴水不漏。多項式時間的硬度結果則是「有條件」的。當我們藉由歸約稱某問題為 NP 困難，我們已證明它至少和 NP 裡每個問題一樣難，但我們「並未」證明它需要指數時間。它們之中是否有任何一個如此，正是那個未解的 P 對 NP 問題——電腦科學裡最著名的未解難題。「NP 完全」意味著「沒有已知的多項式演算法，而其中任一個有了多項式演算法就會給所有問題一個」，而非「不可能存在」。歸約本身堅如磐石；它在 NP 困難這件事上所倚靠的，是一個猜想，說成別的就是撒謊。

退後一步，感受本階的統一。下界說「沒有演算法能做得更好」；我們透過數決策樹葉子、扮演對手，直接掙得了幾個，又藉由歸約便宜地掙得許多更多——借一個已證明的地板，靠一層薄薄的線性包裝，把它帶進元素相異、凸包、最近點對、以及更遠處。而當你爬過本階、進入 NP 完全，唯一的新成分是「便宜」的「尺度」：把線性包裝換成多項式包裝，同樣的借法就把一個難題變成上千個。歸約這個想法，讓硬度一旦在任何地方被建立，就能旅行到每一個需要它的地方。