AFTD Auto-Formalizing Theoretical Domains

PolyTimeRandomizedOnlineCarpoolingAlg

structure

A polynomial-time randomized online carpooling algorithm extends RandomizedOnlineCarpoolingAlg with a step time complexity function step_time : ℕ → ℕ → ℕ such that both step_time and the coin count num_coins are bounded by polynomials in n + T.

Statement

structure PolyTimeRandomizedOnlineCarpoolingAlg extends RandomizedOnlineCarpoolingAlg
Defined in
arXiv:2611.00388 Sec 3.1, Online carpooling against an oblivious adversary
Verified
06 Nov 2026
Axioms
none listed
Built on 1
  • RandomizedOnlineCarpoolingAlgA randomized online carpooling algorithm consists of a function num_coins : ℕ → ℕ → ℕ specifying the number of boolean coins for vertex…

Read back from the Lean

A structure representing a polynomial-time randomized online carpooling algorithm, extending RandomizedOnlineCarpoolingAlg. It consists of: 1. (Inherited from RandomizedOnlineCarpoolingAlg) a function num_coins : ℕ → ℕ → ℕ; 2. (Inherited from RandomizedOnlineCarpoolingAlg) an orientation function orient : (n : ℕ) → (T : ℕ) → List (Fin n × Fin n) → (Fin (num_coins n T) → Bool) → Bool; 3. A function step_time : ℕ → ℕ → ℕ; 4. step_time_poly: a proof that there exists a polynomial p : Polynomial ℕ with natural number coefficients such that for all n, T : ℕ, step_time n T ≤ p.eval (n + T); 5. coins_poly: a proof that there exists a polynomial p : Polynomial ℕ with natural number coefficients such that for all n, T : ℕ, num_coins n T ≤ p.eval (n + T).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A polynomial-time randomized online carpooling algorithm. -/
structure PolyTimeRandomizedOnlineCarpoolingAlg extends RandomizedOnlineCarpoolingAlg where
  step_time : ℕ → ℕ → ℕ
  step_time_poly : ∃ p : Polynomial ℕ, ∀ n T, step_time n T ≤ p.eval (n + T)
  coins_poly : ∃ p : Polynomial ℕ, ∀ n T, num_coins n T ≤ p.eval (n + T)
See it in the graphDiscuss this resultChallenge it