AFTD Auto-Formalizing Theoretical Domains

TarskiQueryTree.cost

def

The number of queries a query tree makes when the black box is f (the length of the path f follows).

Statement

def TarskiQueryTree.cost {n k : ℕ} (f : (Fin k → Fin n) → (Fin k → Fin n)) :
    TarskiQueryTree n k → ℕ
Defined in
arXiv:2610.07055 (Tarski fixed points in quasi-FPT queries), Sec. 1
Verified
07 Oct 2026
Axioms
none listed
Built on 1
  • 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 13
  • 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_leTarski(n, k) ≤ q: some deterministic query algorithm finds a fixed point of every monotone map f : [n]^k → [n]^k (componentwise order)…
  • 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_box_query_le_zero_dimDimension zero is free: in dimension 0 (the one-point box) one query suffices, for every n and every box.
  • tarski_box_query_le_mono_budgetThe box-local query invariant is monotone in the query budget: a box algorithm using at most q queries also satisfies the invariant for…
  • tarski_box_query_leBox-local Tarski query invariant: for every sub-box [a,b] (a ≤ b) of [n]^k there is a single deterministic query tree — depending only on…
  • 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_box_query_le_succ_halvingOne dimension costs a factor log₂ n: from a box-search algorithm in dimension k with q queries one gets one in dimension k+1 with at most…
  • tarski_query_tree_bind_specRun/cost law for sequential composition: the run of a bind is the run of the continuation g at the output of the first tree, and the cost…
  • tarski_query_tree_slice_lift_specRun/cost law for the slice lift: in dimension k+1, the lifted tree computes insertNth i c of the slice algorithm's output (run against the…
  • 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 ≥…
  • tarski_box_query_le_smallBrute force on small boxes: if every box in dimension k has at most M points, then every box query is answerable within M queries — and in…

Lean source view module on GitHub

/-- The number of queries a query tree makes when the black box is `f`. -/
def TarskiQueryTree.cost {n k : ℕ} (f : (Fin k → Fin n) → (Fin k → Fin n)) :
    TarskiQueryTree n k → ℕ := fun
  | .output _ => 0
  | .query x next => (next (f x)).cost f + 1
See it in the graphDiscuss this resultChallenge it