AFTD Auto-Formalizing Theoretical Domains

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
See it in the graphDiscuss this resultChallenge it