TarskiQueryTree
inductive
A deterministic adaptive query algorithm for an unknown map f : [n]^k → [n]^k, as a decision tree: a leaf outputs a point; an internal node queries f at a point x and continues according to the value f(x).
Statement
inductive TarskiQueryTree (n k : ℕ)- Defined in
- arXiv:2610.07055 (Tarski fixed points in quasi-FPT queries), Sec. 1 (the black-box query model; deterministic algorithms as decision trees)
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 17
- 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)…
- TarskiQueryTree.runThe point a query tree outputs when the black box is f.
- 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_query_tree_bindSequential composition of query trees: run the tree, then feed its output point into the continuation g to obtain the tree that is…
- 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.
- TarskiQueryTree.costThe number of queries a query tree makes when the black box is f (the length of the path f follows).
- 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_tree_slice_liftSlice lifting of a query tree one dimension up: replace every query y in dimension k by the query (insertNth i c y) in dimension k+1, and…
- 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
/-- A deterministic adaptive query algorithm for a black-box map `[n]^k → [n]^k`, as a decision tree: a leaf outputs a point; an internal node queries the map at a point and branches on the returned value. -/ inductive TarskiQueryTree (n k : ℕ) | output : (Fin k → Fin n) → TarskiQueryTree n k | query : (Fin k → Fin n) → ((Fin k → Fin n) → TarskiQueryTree n k) → TarskiQueryTree n k