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