平滑分析（smoothed analysis）

演算法裡有個著名的謎題。線性規劃的單純形法（simplex method）在理論上、最壞情況下是指數的——然而六十年來它一直是實務上最快、最可靠的方法之一，幾乎從不展現它的壞行為。最壞情況分析尖叫著「別用它！」；平均情況分析則難以信任，因為它假設輸入抽自某個現實所忽視的理想化隨機分布。平滑分析是化解這個悖論的高明折衷：它問的既不是「絕對最壞的輸入有多糟？」也不是「純隨機的輸入有多好？」，而是「演算法在一個最壞情況輸入、再被輕微隨機擾動之後，表現如何？」。

精確地說：取任何你喜歡的輸入——即使是最對抗性的那個——然後用一個小的隨機量去擾動它（對每個數字加上由參數 sigma 控制其大小的微小隨機雜訊）。平滑執行時間是「對該隨機擾動取期望」的執行時間，然後我們對原始（未擾動）輸入取最壞情況。一個演算法若這個量對「每一個」起始輸入都很小（例如多項式），只要加上一點雜訊，就有良好的平滑複雜度。畫面是這樣：最壞情況執行時間盯著輸入空間中孤立、薄如刀刃的難度尖峰；擾動把每個輸入抹開到一個小鄰域，若那些討厭的尖峰既稀少又脆弱，那一點隨機的輕推幾乎總會把你帶離它們。Spielman 與 Teng 正是對單純形法證明了這件事：它的平滑執行時間是多項式的，所以那些壞情況平衡得如此精巧，以致任何現實世界的不精確（量測雜訊、捨入）都會摧毀它們。

平滑分析之所以重要，是因為它架起理論與實務之間的橋樑：它嚴謹地解釋了為何最壞情況很糟的演算法（單純形、某些區域搜尋方法、一些整數規劃啟發式）在現實世界實際產生的「略帶雜訊」的輸入上運作得很漂亮。它是「超越最壞情況分析」運動的旗艦，該運動尋求比悲觀的最壞情況更忠於真實輸入的模型。誠實的提醒：平滑分析是一種混合度量，不是對每個固定輸入的純粹保證——某個特定的未擾動輸入仍可能很慢，主張談的是擾動後的平均；結論取決於你假設的雜訊模型與大小 sigma（雜訊太少，最壞情況就回來了）；而且它解釋良好的實務行為，並不會把一個最壞情況指數的演算法變成最壞情況多項式的。