莫澤-塔多斯演算法（Moser-Tardos algorithm）
/ MOH-zer TAR-dosh /
莫澤-塔多斯演算法是洛瓦茲局部引理的建構式、演算法版本。經典局部引理證明避開所有壞事件的組態存在，但其證明是個存在性論證，並未給出實際產生一個的有效率方法。數十年來這是個真實的間隙：人們知道好物件就在那裡，卻無法在多項式時間內找到它。2009 年 Robin Moser，隨後 Moser 與 Gabor Tardos 在完全一般的情形下，給出一個出奇簡單的隨機演算法，在與局部引理本質相同的條件下有效率地找到好組態，並附有一個關於它為何快速終止的優美熵壓縮證明。
情境是局部引理的變數版本：壞事件 B_i 由一組互相獨立的隨機變數所決定，每個 B_i 依賴其中一個小子集（其作用域）。演算法直接得近乎令人尷尬。先依各變數的分布抽樣所有變數。然後，當目前有某壞事件 B_i 成立時，挑出這樣一個被違反的事件，並（僅）對其作用域中的變數重新抽樣，依其分布重新抽取；重複。Moser 與 Tardos 證明：若局部引理條件成立（非對稱判準 P(B_i) <= x_i 乘以對相依鄰居 j 的 (1 - x_j) 之積），則此迴圈在期望至多 sum of x_i/(1 - x_i) 次重抽後終止——關於事件數為多項式——並且必然停在一個沒有壞事件的組態。整個正確性論證一頁就能寫完。
它為何終止是深刻之處，而證明本身是熵壓縮方法的旗艦。人們記錄一份執行日誌（哪些事件被重抽的見證樹），並證明一次長執行會讓你把所消耗的隨機位元序列壓縮到短於其自身長度，這是不可能的——隨機性不可被壓縮。這把演算法的執行時間轉化為一個資訊論計數論證。實用收益是：幾乎每個經典局部引理存在性結果（超圖著色、k-SAT、無圈邊著色等）都變成一個多項式時間隨機演算法，參數上本質無損。誠實的提醒是變數模型要求：最簡潔的莫澤-塔多斯定理需要壞事件由具局部作用域的獨立變數定義；把演算法化局部引理推廣到最一般的抽象或偏側情境（Moser-Tardos 分布、超出變數模型的熵壓縮）需要大量進一步的工作，並非免費取得。
k-SAT 的建構化：從一個均勻隨機真值賦值開始。當有某子句未被滿足時，挑一個並對其 k 個變數重新拋擲新的隨機硬幣；重複。若 e * 2^(-k)(d+1) <= 1（局部引理界，d 為子句重疊度），莫澤-塔多斯保證在含 m 個子句的公式上期望 O(m) 次重抽後停止，回傳一組實際的滿足賦值——而不僅是其存在的證明。
對任一被違反事件的變數重新抽樣直到無一被違反——在局部引理條件下可證它快速停止。
簡潔的莫澤-塔多斯結果需要變數模型（事件由局部作用域上的獨立變數定義）；把演算法化與偏側局部引理推廣到此之外是真正的額外工作，並非自動成立。