對手論證（adversary argument）
想像玩一個猜謎遊戲，答案並非事先固定：一個搗蛋的對手盯著你的問題，悄悄把祕密安排得盡可能不方便，同時與已給過的每個答案保持一致。如果不論你問得多聰明，對手都能讓真相保持模糊，直到你問了很多問題，那麼很多問題就是真正必要的。這就是對手論證：一種下界證明，其中一個惡意的「對手」自適應地回答演算法的探查，以逼出大量工作。
具體地說，對手並不先選好輸入。它逐次回答每個比較（或查詢），選那個能讓最多可能輸入存活的答覆，唯一的限制是與之前所有答覆保持一致。演算法不能停，直到只剩一個有效答案。要證明下界為 k，你提出一個對手策略，保證在少於 k 次查詢後，仍有至少兩個一致、但正確答案不同的輸入存活——所以演算法還無法確定，必須再問。一個乾淨的記帳技巧是追蹤對手維護的「狀態」（例如，哪些元素仍可能是最大值候選），並證明每次查詢只能消去有限量的不確定性。
對手論證之所以強大，是因為它是自適應的：對手依演算法剛做了什麼來量身回答，往往得出比靜態計數論證更緊的下界。它證明了本領域中一些最漂亮的精確界——找最大值需 n-1 次比較，同時找最大與最小需 ceil(3n/2) - 2 次。誠實的提醒：對手「絕不可」與先前答案矛盾（它隱含維護的輸入必須始終一致），否則證明無效；而且如同這些技巧，此界是最壞情況且依模型而定。一個正確的對手論證能證明該下界對模型中每個決定性演算法都成立，因為對手可以對任何一個做出反應。
找 n 個數的最大值：對手堅持每個元素在輸掉一次比較之前都「仍可能是最大值」。每次比較最多淘汰一個候選，而要確定贏家，全部 n-1 個輸家都必須被淘汰，所以至少逼出 n-1 次比較——恰好與顯而易見的演算法吻合。
對手自適應地回答，讓真相保持模糊，逼演算法繼續發問。
對手必須保持一致：始終得存在至少一個與它給過的每個答案相符的真實輸入，否則論證什麼也沒證明。它是證明工具，不是真的對手——它顯示每個演算法在最壞情況下必須面對什麼。