PMTree.run
def
The output of the algorithm T on the poset P.
Statement
open Finset in def PMTree.run {n : ℕ} : PMTree n → PMPoset n → Finset (Fin n)
- 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 3
- PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
- PMPoset.ansThe comparison oracle: the answer to query (a, b) on the poset P.
- PMTreeA deterministic adaptive comparison algorithm, as a decision tree: a leaf outputs a set, an internal node queries the pair (a, b) and…
- Used by 3
- pm_mainMain adversary lemma: against any decision tree that is correct on all width-2 posets consistent with the answers so far, the adversary…
- PMTree.Correct2T correctly finds the minimal elements of every poset of width at most 2 on Fin n.
- pm_alg_runCorrectness of the candidate-list algorithm on width-2 posets.
Lean source view module on GitHub
open Finset in /-- The output of the algorithm `T` on the poset `P`. -/ def PMTree.run {n : ℕ} : PMTree n → PMPoset n → Finset (Fin n) := fun | PMTree.leaf s, _ => s | PMTree.node a b k, P => (k (P.ans a b)).run P