AFTD Auto-Formalizing Theoretical Domains

PMTree.cost

def

The number of queries the algorithm T makes on the poset P.

Statement

def PMTree.cost {n : ℕ} : PMTree n → PMPoset 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 6
  • pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
  • 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…
  • 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_alg_cost_leThe algorithm makes at most 2n − 3 queries (for n ≥ 2).
  • 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…

Lean source view module on GitHub

/-- The number of queries the algorithm `T` makes on the poset `P`. -/
def PMTree.cost {n : ℕ} : PMTree n → PMPoset n → ℕ := fun
  | PMTree.leaf _, _ => 0
  | PMTree.node a b k, P => (k (P.ans a b)).cost P + 1
See it in the graphDiscuss this resultChallenge it