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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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