PMPoset.ans
def
The comparison oracle: the answer to query (a, b) on the poset P.
Statement
def PMPoset.ans {n : ℕ} (P : PMPoset n) (a b : Fin n) : PMAns- Defined in
- Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4: Theorem 11, Theorem 16 and the conjecture that the deterministic lower bound for k = 1 is tight; formalized by the operator (Claude), 2026-10-05
- Verified
- 05 Oct 2026
- Axioms
- none listed
- Built on 2
- Used by 17
- pm_ans_incIf the oracle answers that a and b are incomparable, neither a < b nor b < a holds.
- pm_rerankChanging an alive element's rank to anything below n + #alive does not change any recorded answer (used both for the adversary's "kill"…
- pm_inv_killAdversary case: comparison of two alive elements of the same component and colour; the larger one (z) dies and is re-ranked just below all…
- pm_ans_famExplicit form of the oracle on a two-chain poset.
- PMSatA list of query/answer facts is satisfied by P.
- PMTree.runThe output of the algorithm T on the poset P.
- pm_ans_ltIf the oracle answers a < b then a < b holds and b < a does not.
- pm_inv_mergeAdversary case: two different components are merged (answer ∥); the second component is recoloured if necessary. The number of components…
- PMState.stepThe adversary's move on query (a, b): the answer, and the new state.
- pm_recolorRecolouring that preserves colour-equality on every fact preserves all answers.
- pm_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…
- pm_ans_gtIf the oracle answers b < a then b < a holds and a < b does not.
- PMTree.costThe number of queries the algorithm T makes on the poset P.
- pm_inv_deadAdversary case: same component and colour, not both alive (answer read off the current two-chain realisation).
- pm_alg_costCost bound: at most two queries per element, one for the second element, none for the first.
- pm_step_invEvery adversary move keeps the invariant and lowers the potential by at most one.
- pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.
Lean source view module on GitHub
/-- The comparison oracle: the answer to query `(a, b)` on the poset `P`. -/ def PMPoset.ans {n : ℕ} (P : PMPoset n) (a b : Fin n) : PMAns := if P.lt a b then PMAns.lt else if P.lt b a then PMAns.gt else PMAns.inc