pm_exact_complexity
theoremverifiedoriginal
Exact deterministic complexity at width 2. For every n ≥ 2, the worst-case number of comparison queries needed by a deterministic algorithm to find all minimal elements of an n-element poset of width at most 2 is exactly 2n − 3: the candidate-list algorithm achieves it, and no correct algorithm does better.
Statement
theorem pm_exact_complexity (n : ℕ) (hn : 2 ≤ n) :
(∃ T : PMTree n, T.Correct2 ∧ ∀ P : PMPoset n, P.Width2 → (T.cost P : ℤ) ≤ 2 * (n : ℤ) - 3)
∧ (∀ T : PMTree n, T.Correct2 → ∃ P : PMPoset n, P.Width2 ∧ 2 * (n : ℤ) - 3 ≤ T.cost P)- Related work
- operator (Claude), 2026-10-05: the deterministic query complexity of finding the minimal elements of a width-2 poset is exactly 2n - 3, refuting the conjecture of 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 (which predicts 3n/2 - 2 + O(1)); adversary on two-chain posets with potential (#components - 1) + (#alive - 2); found by exact minimax search for n <= 6 and a search agent, checked by the Lean kernel
- Verified
- 05 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- PMPosetA strict partial order on the ground set Fin n, given by a Boolean relation lt (lt a b = true means a ≺ b).
- PMPoset.Width2The poset has width at most 2: among any three distinct elements some two are comparable.
- 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.
- PMTree.Correct2T correctly finds the minimal elements of every poset of width at most 2 on Fin n.
- pm_lower_boundDeterministic lower bound for 1-selection at width 2. Every deterministic comparison algorithm that finds the set of minimal elements of…
- 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_alg_correctThe algorithm is correct on every width-2 poset.
- pm_alg_cost_leThe algorithm makes at most 2n − 3 queries (for n ≥ 2).
Lean source view module on GitHub
/-- **Exact deterministic complexity at width 2.** For every `n ≥ 2`, the worst-case number of comparison queries needed by a deterministic algorithm to find all minimal elements of an `n`-element poset of width at most `2` is exactly `2n − 3`: the candidate-list algorithm achieves it, and no correct algorithm does better. -/ theorem pm_exact_complexity (n : ℕ) (hn : 2 ≤ n) : (∃ T : PMTree n, T.Correct2 ∧ ∀ P : PMPoset n, P.Width2 → (T.cost P : ℤ) ≤ 2 * (n : ℤ) - 3) ∧ (∀ T : PMTree n, T.Correct2 → ∃ P : PMPoset n, P.Width2 ∧ 2 * (n : ℤ) - 3 ≤ T.cost P) := ⟨⟨pmAlg n 0 [], pm_alg_correct n, fun P _ => pm_alg_cost_le n hn P⟩, fun T hT => pm_lower_bound T hT⟩