熵壓縮方法（entropy compression method）

熵壓縮方法是一種證明技巧，由 Moser 對演算法化局部引理的分析提煉而來，它藉由證明「若演算法執行太久就能讓你把一串隨機位元壓縮到短於其自身長度，而這在資訊論上不可能」來界定隨機演算法的執行時間——並因此證明存在性。它立基於這個基石事實：均勻隨機的位元串平均而言無法被壓縮：任何對 n 位元串的單射編碼，對其中某些必須至少用 n 位元。所以若一個假想的長執行會產生過短的編碼，該執行便不能發生。它是一個偽裝成熱力學論證的計數論證。

其機制如下運作。執行一個消耗新鮮隨機位元的隨機演算法，每當它碰到壞組態便採取一個修正步驟（如 Moser-Tardos 重抽）。維護一份日誌，以緊湊形式記錄演算法歷史中足以精確重建用了哪些隨機位元的資訊。竅門在於設計日誌，使長度為 T 的執行被編碼成嚴格短於其所消耗 T 個隨機位元的字串——通常是因為修正步驟的結構（一棵見證樹、一串約束索引）高度受限，故攜帶的資訊少於原始隨機性。若編碼是單射且短於其輸入，則相異的隨機位元序列會映到比序列數更少的碼字，這在 T 大時是矛盾。因此 T 必須小：演算法快速終止，並達到一個好組態。存在性是快速終止的副產品。

其意義有二。第一，它在較早方法（經典局部引理）只給出非建構式存在之處給出建構式、多項式時間的證明，而且這些證明往往比原版更短更透明。第二，它本身已成為一個靈活工具，遠用於局部引理之外——例如證明圖的不重複（無平方）著色、模式避免與無圈邊著色中的界，有時給出比局部引理更佳的常數。誠實的提醒是此方法需要一個真正巧妙、針對問題的編碼：整個證明取決於證明日誌是單射且短的，而沒有自動的配方——草率的編碼要麼不可重建（非單射）要麼實際上並不更短，於是論證崩潰。它界定的是期望或典型執行時間與存在性；它不是萬靈丹，本身也不給出最銳利可能的門檻。