PMTree
inductive
A deterministic adaptive comparison algorithm, as a decision tree: a leaf outputs a set, an internal node queries the pair (a, b) and branches on the answer.
Statement
inductive PMTree (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 1
- PMAnsThe three possible answers of a comparison query (a, b) on a poset: a ≺ b, b ≺ a, or a ∥ b (incomparable). Setting of arXiv 0707.1532…
- Used by 10
- pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
- PMTree.runThe output of the algorithm T on the poset P.
- pm_conjecture_falseThe conjecture of arXiv 0707.1532 (Section 4) that the deterministic lower bound (w+1)n/2 − w for finding the minimal elements is tight…
- pmAlgThe candidate-list algorithm (Theorem 11 of arXiv 0707.1532, for width 2): scan the elements in order, keeping the (at most two) minimal…
- 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.costThe number of queries the algorithm T makes on the poset P.
- pm_alg_costCost bound: at most two queries per element, one for the second element, none for the first.
- pm_exact_complexityExact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic…
- 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
/-- A deterministic adaptive comparison algorithm, as a decision tree: a leaf outputs a set, an internal node queries the pair `(a, b)` and branches on the answer. -/ inductive PMTree (n : ℕ) | leaf : Finset (Fin n) → PMTree n | node : Fin n → Fin n → (PMAns → PMTree n) → PMTree n