Non-adaptive deterministic query complexity
Fewest queries when the whole query set must be fixed in advance.
also written:
oblivious decision tree complexity, number of relevant variables (total f)
Definition
The algorithm chooses a set $S \subseteq [n]$ before seeing the input, learns $x|_S$, and must then output $f(x)$. $\mathrm{D}^{\mathrm{na}}(f)$ is the smallest such $|S|$.
For total $f$ this is exactly the number of relevant variables: $S$ works iff $f$ does not depend on any coordinate outside $S$. For partial $f$ it is smaller and less trivial -- $S$ only has to determine $f$ on the promise.
Basic facts
- $\mathrm{D}(f) \le \mathrm{D}^{\mathrm{na}}(f) \le n$.
- Adaptivity can save exponentially: $\mathrm{D}(\mathrm{ADDR}) = \log_2 n + 1$ while $\mathrm{D}^{\mathrm{na}}(\mathrm{ADDR}) = n + \log_2 n$, since every data bit is relevant.
- The other direction is exponential, not unbounded: $\mathrm{D}^{\mathrm{na}}(f) \le 2^{\mathrm{D}(f)}-1$, since a depth-$\mathrm{D}$ tree has at most that many internal nodes and so touches at most that many variables. Binary tree navigation $\mathrm{Nav}_k$ attains it exactly.
- $\mathrm{D}^{\mathrm{na}}(f) \ge \mathrm{s}(f)$, $\mathrm{bs}(f)$, $\mathrm{deg}(f)$ and every other measure, since all of them are supported on relevant variables.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{D}^{\mathrm{na}}(f)\). “\(\mathrm{D}^{\mathrm{na}}(f)\) in terms of it” is the pair with \(\mathrm{D}^{\mathrm{na}}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(n\) | Every variable is relevant. |
| AND total | \(n\) | Every variable is relevant. |
| PARITY total | \(n\) | |
| MAJORITY total | \(n\) | Every variable is relevant. |
| Threshold total | \(n\) | |
| Symmetric functions (general) total | \(n\) | A non-degenerate symmetric function depends on every coordinate. |
| EXACT-HALF total | \(n\) | |
| ODD-MAX-BIT total | \(n\) | |
| ADDRESS / multiplexer total | \(k + 2^k\) | Every data bit is relevant, so a non-adaptive algorithm reads the entire table. |
| Binary tree navigation total | \(2^k - 1\) | Every variable is relevant: for the node $v$, take the input whose walk reaches $v$ and whose two subtrees below $v$ lead to bottom bits of opposite value. So a non-adaptive algorithm must read all of them, and $\mathrm{D}^{\mathrm{na}} = 2^{\mathrm{D}}-1$ exactly -- the extreme case of the bound $\mathrm{D}^{\mathrm{na}} \le 2^{\mathrm{D}}-1$. |
| TRIBES total | \(n\) | Every variable is relevant. |
| AND-OR tree (depth 2) total | \(N = n^2\) | |
| NAND tree (balanced AND-OR formula) total | \(N\) | |
| Recursive MAJORITY-of-3 total | \(N = 3^d\) | |
| Kushilevitz's function (iterated) total | \(N\) | |
| Rubinstein's function total | \(N\) | |
| Ambainis-Sun function total | \(N = 12k^2+14k+4\) | Every variable is relevant, and a non-adaptive algorithm must read every relevant variable. |
| AND composed with NOT-EXACT-HALF total | \(N = n^2\) | Every variable is relevant, and a non-adaptive algorithm must read every relevant variable. |
| Meiburg's tournament-subcube function total | \(\ge 14011^{\,d}\) putative | Non-adaptivity only costs more: $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D} \ge \mathrm{bs}$. |
| Pointer functions total | \(\widetilde\Theta(n)\) | Squeezed between $\mathrm{D}=\widetilde\Omega(n)$ and the input length $n$. |
| Cheat-sheet functions total | \(\widetilde\Omega(n)\) | Squeeze: $\mathrm{D}^{\mathrm{na}}\ge\mathrm{D}=\widetilde\Omega(n)$; the ceiling is again the input length $n^{10+o(1)}$ rather than anything in the $n$-scale. |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n^3)\) | Squeeze: $\mathrm{D}^{\mathrm{na}}\ge\mathrm{D}$. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Omega(n^2)\) | Squeeze: $\mathrm{D}^{\mathrm{na}}\ge\mathrm{D}$; the ceiling is the arity $\widetilde\Theta(n^4)$. |
| Gilmer-Saks-Srinivasan functions total | \(n^2\) | Squeeze: $\mathrm{D}\le\mathrm{Dna}\le N=n^2$. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Theta(n)\) | Squeezed between $\mathrm{D}=\widetilde\Omega(n)$ and the input length $n$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Omega(n^{2/3})\) | Squeeze: $\mathrm{D}^{\mathrm{na}}\ge\mathrm{D}$. |
| Ambainis' exact-quantum function total | \(3^d\) | Squeeze: $\mathrm{D}\le\mathrm{Dna}\le n$. |
| FORRELATION partial | \(\Theta(n)\) | Between $\mathrm{D} = \Theta(n)$ and the trivial $2n$. |
| k-FORRELATION partial | \(O(kn)\) | The whole input, fixed in advance; and $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$. |
| Simon's problem partial | \(\Theta(2^{n/2})\) putative | The $A\cup B$ query set above is fixed in advance, so the deterministic upper bound is already non-adaptive; and $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$. |
| Deutsch-Jozsa partial | \(N/2+1\) putative | Adaptivity is worthless here: any fixed $N/2+1$ positions contain a $0$ and a $1$ of every balanced input (which has exactly $N/2$ of each), so reading them decides. And $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$. |
| Bernstein-Vazirani partial | \(n\) putative | The spanning set $e_1,\dots,e_n$ is fixed in advance, and $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$. |
| Marked bit partial | \(n\) putative | Adaptivity buys nothing: the $y_b$ algorithm is already non-adaptive, and the lower bound above needs one query per cell whatever the order. |
| Dense marked bit partial | \(n/2+1\) putative | The $\mathrm{D}$ upper bound is already non-adaptive -- a fixed set of $n/2+1$ $y$-bits determines the answer -- and $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$. |
| Unstructured search (relation) relation | \(n\) | Adaptivity buys nothing: $\mathrm{D} = n$ already, and reading the whole input non-adaptively also costs $n$. |
| FIND-1 under a density promise relation | \(n/2+1\) putative | A fixed set of $n/2+1$ positions must contain a $1$ (a promise input has at most $n/2$ zeros), and a fixed set of $n/2$ positions can be entirely zero. So adaptivity is worth nothing on the deterministic side either -- all the power is in the coins. |
| Approximate Hamming weight relation | \(\Theta(n)\) | Between $\mathrm{D}=\Theta(n)$ and the trivial $n$. |
| Correlated-string search relation | \(\Theta(n)\) putative | The deterministic algorithm above is non-adaptive, and the adversary argument does not care about adaptivity. |
| SearchCNF relation | \(n\) | Every variable is relevant, so a non-adaptive algorithm reads the whole assignment. |
| Gap-Majority partial | \(\Theta(n)\) | Between $\mathrm{D} = \Theta(n)$ and the trivial $n$; the adversary count for $\mathrm{D}$ never used adaptivity anyway. |
| Gap-Majority at constant gap partial | \(\Theta(n)\) | Between $\mathrm{D}$ and $n$; the adversary count never used adaptivity. |
| Parity-labelled FIND-1 partial | \(n/4+1\) putative | The same count as $\mathrm{D}$, which never used adaptivity: a fixed set missing $n/4$ odd and $n/4$ even positions is consistent with both answers, and a fixed set of $n/4+1$ odd positions decides. So all the power here is in the coins, not in adaptivity. |
| Approximate index partial | \(\Theta(\sqrt{k\log k})\) putative | Adaptivity is worth nothing: read the first $4\sqrt{k\log k}$ bits of $a$ and query both antipodal completions $x_b$ and $x_{b'}$ at once -- one of them is inside the ball. And $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D}$. Note the lemma "$\mathrm{D}^{\mathrm{na}} = n$ for functions depending on all variables" does not apply here: with $\mathrm{s} = 0$, no single coordinate is relevant within the promise. |
| Collision problem partial | \(n/2+1\) putative | The same $n/2+1$ positions, fixed in advance. |
| Element distinctness total | \(n\) | Every symbol is relevant, so a non-adaptive algorithm reads all of them -- which here costs nothing, since $\mathrm{D}=n$ anyway. |
| Ambainis-Belovs function partial | \(O(n)\) | The same $3n$ positions, fixed in advance. |
| Ben-David-Kundu total search problems relation | \(\widetilde\Omega(\sqrt n)\) | At least $\mathrm{D}$. |
| Yamakawa-Zhandry problem relation | \(2^{\Omega(n)}\) | At least $\mathrm{D}$. |
| Surjectivity total | \(n\) | Every bit is relevant -- permute the list so that the slot in question holds a uniquely-occurring value, and flipping any of its bits changes the answer -- so for a total function the non-adaptive cost is the full $n$. Consistent with $\mathrm{D} = \mathrm{D}^{\mathrm{na}} = n$: adaptivity buys nothing here. |
| $k$-distinctness total | \(n\) | Every symbol is relevant, so a non-adaptive algorithm reads all of them; $\mathrm{D} = n$ anyway. |
| Triangle finding total | \(\binom m2 = n\) | Every edge is relevant, so a non-adaptive deterministic algorithm reads the whole adjacency matrix -- which costs nothing extra, since the property is evasive. |
| Recursive Fourier sampling partial | \(O(n^{\ell})\) putative | Adaptivity buys nothing: the $O(n^{\ell})$ deterministic algorithm of the $\mathrm{D}$ entry is already non-adaptive. Its query set is fixed in advance -- the $n^{\ell}$ leaves $(e_{i_1},\dots,e_{i_\ell})$ whose every path component is a standard basis vector -- and the recursion $s_v\cdot e_i = g(s_{v e_i})$ then reconstructs every secret bottom-up. So $\mathrm{D} \le \mathrm{D}^{\mathrm{na}} \le n^{\ell}$, and at $\ell = \log n$ both are $n^{\Theta(\log n)}$. |
| Welded trees relation | \(\Theta(4^n)\) putative | Adaptivity is not a convenience here, it is the whole problem: $\mathrm{D}^{\mathrm{na}}/\mathrm{D} = \tilde\Theta(2^{3n/2})$. A non-adaptive algorithm must fix its query names in advance knowing only $\pi(\mathrm{ENTRANCE})$, and the $2^{n+2}-2$ real names are a $2^{-n+2}$ fraction of the $2^{2n}$ name space. Upper: query all $9\cdot 2^{2n}$ (name, colour) pairs and reconstruct the graph. Lower: let $S$ be the set of names queried. The transcript reveals $\pi(\mathrm{EXIT})$ only if $\mathrm{EXIT}$ or one of its $\le 3$ neighbours lies in $S$; if not, and if some name outside $S$ is unused, swapping $\pi(\mathrm{EXIT})$ with that name leaves the transcript unchanged and the required output different. So $|S| \ge 2^{2n} - 2^{n+2} - 1$. |
| Local search on the hypercube relation | \(2^n\) putative | Every cell -- that is, the whole table, $N = 2^n$ -- and the loss against $\mathrm{D} = \Theta(2^n/\sqrt n)$ is only the $\sqrt n$. Suppose the fixed query set $S$ omits the cell $u$ and let $f$ agree on $S$ with the Hamming distance to $u$. If $f(u) = 0$ then $u$ is the unique local minimum, while if $f(u)$ is huge the local minima are exactly the $n$ neighbours of $u$; the transcript is the same in both cases and the required output differs, so $S$ must be everything. |
| Local search on the grid relation | \(k^d = N\) putative | Every cell, for every $d \ge 1$, so non-adaptivity is catastrophic already at $d = 2$ where $\mathrm{D} = \Theta(k)$. If the fixed query set $S$ omits the cell $u$, let $f$ agree on $S$ with the $\ell_1$ distance to $u$: when $f(u) = 0$ the unique local minimum is $u$, and when $f(u)$ is huge the local minima are exactly the neighbours of $u$. Same transcript, different required output. |
| Fourier fishing relation | \(N\) | Trivially, since $\mathrm{D}^{\mathrm{na}} \ge \mathrm{D} = N$ and reading the whole truth table is non-adaptive. Adaptivity is worth nothing here, which is the mirror image of \(\mathrm{WT}_n\). |
| Ordered search partial | \(n\) putative | A fixed query set $S$ tells you only which gap of $S$ the boundary $k$ falls into, i.e. an interval of candidate $k$; the $|S|+1$ intervals must all be singletons to determine the parity, and there are $n+1$ candidates, so $|S| \ge n$. Adaptivity is worth an exponential factor here -- the largest possible, since $\mathrm{D}^{\mathrm{na}} \le n$ always. |
| Tseitin search on an expander relation | \(n\) | Between $\mathrm{D} = \Theta(n)$ and the trivial $n$. |
| Inner product mod 2 total | \(n\) | Every variable is relevant, so non-adaptively you read all of them. |
| Minsky-Papert one-in-a-box total | \(N = m^3\) | Every variable is relevant. |
| Sink of a tournament total | \(N = \binom m2\) | Every edge is relevant. |
| Scorpion graphs total | \(\binom{m}{2} = N\) putative | Every pair $uv$ is sensitive somewhere -- take the scorpion with sting $u$, tail $v$ -- so a fixed query set that omits $uv$ fails to separate that scorpion from its neighbour. Hence all $N$ bits must be read in advance, against $\mathrm{D} = \Theta(\sqrt N)$. (The $\mathrm{D}^{\mathrm{na}} = N$ half is the generic fact that a non-adaptive algorithm must read every relevant variable; what is special here is how small $\mathrm{D}$ is.) \(\mathrm{Nav}_k\) pushes the same phenomenon to an exponential gap; the scorpion is the natural graph-theoretic instance. |
| Graph connectivity total | \(\binom{m}{2} = N\) | Every pair is relevant, so a non-adaptive algorithm reads everything. Here that is no loss at all: $\mathrm{D}=N$ already, connectivity being evasive. |