AFTD Auto-Formalizing Theoretical Domains

pm_alg_cost

theoremverified

Cost bound: at most two queries per element, one for the second element, none for the first.

Statement

theorem pm_alg_cost {n : ℕ} (P : PMPoset n) : ∀ (m k : ℕ) (cs : List (Fin n)),
    cs.length ≤ 2 →
    ((pmAlg m k cs).cost P : ℤ) ≤ max 0 (2 * (m : ℤ) -
      (if cs.length = 0 then 3 else if cs.length = 1 then 1 else 0))
Source
step towards pm_exact_complexity / pm_lower_bound (exact complexity 2n - 3 at width 2, refuting the tightness conjecture of Sorting and Selection in Posets, SODA 2009 / SIAM J. Comput. 2011 (arXiv:0707.1532), Section 4)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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…
  • PMTree.costThe number of queries the algorithm T makes on the poset P.
  • pmAlgThe candidate-list algorithm (Theorem 11 of arXiv 0707.1532, for width 2): scan the elements in order, keeping the (at most two) minimal…
Used by 1
  • pm_alg_cost_leThe algorithm makes at most 2n − 3 queries (for n ≥ 2).

Lean source view module on GitHub

/-- Cost bound: at most two queries per element, one for the second element, none for the first. -/theorem pm_alg_cost {n : ℕ} (P : PMPoset n) : ∀ (m k : ℕ) (cs : List (Fin n)),    cs.length ≤ 2 →    ((pmAlg m k cs).cost P : ℤ) ≤ max 0 (2 * (m : ℤ) -      (if cs.length = 0 then 3 else if cs.length = 1 then 1 else 0)) := by  intro m  induction m with  | zero =>    intro k cs _    simp [pmAlg, PMTree.cost]  | succ m ih =>    intro k cs hlen    by_cases hk : k < n    · rcases cs with _ | ⟨t, _ | ⟨t2, _ | ⟨t3, rest⟩⟩⟩      · have := ih (k + 1) [⟨k, hk⟩] (by simp)        simp only [pmAlg, dif_pos hk]        simp at this ⊢        omega      · have h1 := ih (k + 1) [⟨k, hk⟩] (by simp)        have h2 := ih (k + 1) [t] (by simp)        have h3 := ih (k + 1) [t, ⟨k, hk⟩] (by simp)        simp only [pmAlg, dif_pos hk, PMTree.cost]        simp at h1 h2 h3 ⊢        cases P.ans ⟨k, hk⟩ t <;> simp <;> push_cast <;> omega      · have h1 := ih (k + 1) [⟨k, hk⟩] (by simp)        have h2 := ih (k + 1) [t, t2] (by simp)        have h3 := ih (k + 1) [t2, ⟨k, hk⟩] (by simp)        have h4 := ih (k + 1) [t, ⟨k, hk⟩] (by simp)        simp only [pmAlg, dif_pos hk, PMTree.cost]        simp at h1 h2 h3 h4 ⊢        cases P.ans ⟨k, hk⟩ t <;> (try simp [PMTree.cost]) <;>          cases P.ans ⟨k, hk⟩ t2 <;> (try simp) <;> push_cast <;> omega      · simp at hlen    · simp only [pmAlg, dif_neg hk, PMTree.cost]      simp
See it in the graphDiscuss this resultChallenge it