AFTD Auto-Formalizing Theoretical Domains

tarski_query_complexity_le

def

Tarski(n, k) ≤ q: some deterministic query algorithm finds a fixed point of every monotone map f : [n]^k → [n]^k (componentwise order) using at most q queries.

Statement

def tarski_query_complexity_le (n k q : ℕ) : Prop
Defined in
arXiv:2610.07055 (Tarski fixed points in quasi-FPT queries), Sec. 1 (deterministic query complexity of Tarski(n, k)); the grid is {0, …, n−1}^k instead of {1, …, n}^k
Verified
07 Oct 2026
Axioms
none listed
Built on 3
  • TarskiQueryTree.runThe point a query tree outputs when the black box is f.
  • TarskiQueryTree.costThe number of queries a query tree makes when the black box is f (the length of the path f follows).
  • TarskiQueryTreeA deterministic adaptive query algorithm for an unknown map f : [n]^k → [n]^k, as a decision tree: a leaf outputs a point; an internal…
Used by 6
  • tarski_query_complexity_mono_budgetQuery complexity is monotone in the query budget: any algorithm using at most q queries also satisfies the bound for any q' ≥ q.
  • tarski_query_complexity_dim_le_succDimension reduction: any query algorithm finding a fixed point in dimension k + 1 in at most q queries can be simulated in dimension k…
  • tarski_box_query_le_imp_query_complexityThe box-local invariant implies the ambient query complexity notion, by taking the full box [0, n−1]^k (needs n ≥ 1 since Fin n has no…
  • tarski_query_complexity_dim_leGeneral dimension simulation reduction: any query algorithm finding a fixed point in dimension k in at most q queries can be simulated in…
  • tarski_query_complexity_one_le_logOne-dimensional Tarski by binary search: for n ≥ 1, a fixed point of any monotone map on the chain {0, …, n−1} can be found with at most…
  • tarski_query_complexity_le_polylogMultidimensional Tarski search is polylogarithmic: for every fixed k there is a constant C with Tarski(n,k) ≤ C·(log₂ n + 2)^k for all n ≥…

Lean source view module on GitHub

/-- `Tarski(n, k) ≤ q`: some deterministic query algorithm finds a fixed point of every monotone map `f : [n]^k → [n]^k` (componentwise order) with at most `q` queries. -/
def tarski_query_complexity_le (n k q : ℕ) : Prop :=
  ∃ t : TarskiQueryTree n k, ∀ f : (Fin k → Fin n) → (Fin k → Fin n), Monotone f →
    f (t.run f) = t.run f ∧ t.cost f ≤ q
See it in the graphDiscuss this resultChallenge it