AFTD Auto-Formalizing Theoretical Domains

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