Q The Query Complexity Zoo
\(\mathrm{R}^{\mathrm{na}}(f)\)

Non-adaptive randomized query complexity

Bounded-error cost when the query set is drawn from a distribution fixed in advance, independent of the answers.

also written: oblivious randomized decision tree complexity

Definition

The algorithm samples a set $S \subseteq [n]$ from a distribution of its choosing, learns $x|_S$, and outputs a guess that must be correct with probability $\ge 2/3$. $\mathrm{R}^{\mathrm{na}}_\varepsilon(f)$ is the least $\max |S|$ over the support (the worst-case version; the expected-cost version is the natural companion, as for $\bar{\mathrm{R}}$).

Non-adaptivity is the standard restriction in property testing, where "adaptive vs non-adaptive" is one of the two axes (the other being one-sided vs two-sided error).

Parameters

\(\varepsilon\) (eps) default \(1/3\)

error probability

Basic facts

  • $\mathrm{R}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, and in the other direction $\mathrm{R}^{\mathrm{na}}_\varepsilon(f) \le 2^{\mathrm{R}_\varepsilon(f)}-1$: sample a tree from the optimal distribution and read every variable it could ever query.
  • Yao's minimax applies verbatim: $\mathrm{R}^{\mathrm{na}}_\varepsilon(f) = \max_\mu \mathrm{D}^{\mathrm{na},\mu}_\varepsilon(f)$, the max over input distributions of the best fixed query set of that size.
  • Adaptivity can save exponentially even with randomness: $\mathrm{R}(\mathrm{ADDR}) = \Theta(\log n)$ while $\mathrm{R}^{\mathrm{na}}(\mathrm{ADDR}) = \Theta(n)$, since a fixed distribution over $k$ data bits finds the addressed bit with probability $\le k/n$ and must otherwise guess.
  • For $\mathrm{OR}_n$ adaptivity buys nothing: $\mathrm{R}(\mathrm{OR}_n) = \Theta(n) = \mathrm{R}^{\mathrm{na}}(\mathrm{OR}_n)$.
  • Non-adaptively, noise is free to resist: $\mathrm{R}^{\mathrm{na}}(f) = \Theta(\mathrm{noisyR}^{\mathrm{na}}(f))$ for every partial Boolean $f$ [BenDavidBlais20composition, Thm. 8], although the same statement is false for relations. Contrast the adaptive case, where $\mathrm{noisyR}$ can be exponentially smaller than $\mathrm{R}$.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{R}^{\mathrm{na}}(f)\). “\(\mathrm{R}^{\mathrm{na}}(f)\) in terms of it” is the pair with \(\mathrm{R}^{\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.

Other measure \(\mathrm{R}^{\mathrm{na}}(f)\) in terms of it It in terms of \(\mathrm{R}^{\mathrm{na}}(f)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity totalexp,exp partialexp,exp relationexp,exp open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity total1,1 partial1,1 relation1,1 open pair → total1,? partial∞ relation∞ derived open pair →
\(\mathrm{D}(f)\) Deterministic query complexity totalexp,? partialexp,? relationexp,? derived open pair → total1,3 partial∞ relation∞ derived open pair →
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity total1,1 partial1,1 relation∞ open pair → total1,1 partial1,1 relation1,1 open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(n)\) A fixed distribution over query sets of size $m$ leaves some coordinate unqueried with probability $\ge 1-m/n$, and $0^n$ versus $e_i$ is then undecidable; so $m=\Omega(n)$.
AND total \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$ here.
PARITY total \(n\) Leaving any coordinate unqueried leaves the answer a fair coin flip.
MAJORITY total \(\Theta(n)\) In fact $n - O(1)$, which is sharper than the recorded $\Theta(n)$ but mixes an exact and an asymptotic term, so it lives here rather than in the value. If two coordinates go unqueried the remaining $n-2$ bits can be set to split evenly, and then the two unread bits decide the answer, leaving it a fair coin flip; so every non-adaptive query set must miss at most one coordinate and $\mathrm{R}^{\mathrm{na}} \ge n-1$. The matching $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = n$ is trivial.
Threshold total \(\Theta(n)\)
Symmetric functions (general) total \(\Theta(n)\) Sandwiched between $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$.
EXACT-HALF total \(\Theta(n)\) Sandwiched: $\widetilde{\deg}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\widetilde{\deg}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$ here.
ODD-MAX-BIT total \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$ here.
ADDRESS / multiplexer total \(\Theta(2^k)\) A fixed distribution over $m$ data bits contains the addressed one with probability at most $m/2^k$; otherwise the algorithm is guessing an unbiased bit.
Binary tree navigation total \(\Theta(2^k)\) On a uniformly random input the bottom node reached is uniform over the $2^{k-1}$ bottom nodes, and an algorithm that has not read it is guessing an unbiased bit; a fixed set of $m$ variables contains it with probability at most $m/2^{k-1}$.
TRIBES total \(\Theta(n)\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R}_{\varepsilon}(f) = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}}(f) = n$ here.
AND-OR tree (depth 2) total \(\Theta(n^2) = \Theta(N)\) Between $\mathrm{R} = \Theta(n^2)$ and $\mathrm{D}^{\mathrm{na}} = n^2$.
NAND tree (balanced AND-OR formula) total \(\Theta(N)\) putative Non-adaptive randomness buys nothing on any function that depends on all its variables. Pick a uniformly random leaf $\ell$ and a fixed input making $\ell$ pivotal, then set $x_\ell$ uniformly at random. A non-adaptive algorithm reading $q$ positions hits $\ell$ with probability $\le q/N$, and otherwise sees a fixed string and must guess a uniform bit, so its success probability is at most $\tfrac12 + \tfrac{q}{2N}$. Hence $\mathrm{R}^{\mathrm{na}}_{1/3}(f) \ge N/3$ for every $f$ with all $N$ variables relevant, matching $\mathrm{D}^{\mathrm{na}} = N$. This is the general form of the \(\mathrm{ADDR}_k\) argument already recorded on the \(\mathrm{R}^{\mathrm{na}}(f)\) page, and it separates $\mathrm{R}^{\mathrm{na}} = \Theta(N)$ from $\mathrm{R} = \Theta(N^{0.753\ldots})$ here.
Recursive MAJORITY-of-3 total \(\Theta(N) = \Theta(3^{\,d})\) putative Non-adaptive randomness buys nothing on any function that depends on all its variables. Pick a uniformly random leaf $\ell$ and a fixed input making $\ell$ pivotal, then set $x_\ell$ uniformly at random. A non-adaptive algorithm reading $q$ positions hits $\ell$ with probability $\le q/N$, and otherwise sees a fixed string and must guess a uniform bit, so its success probability is at most $\tfrac12+\tfrac{q}{2N}$; hence $\mathrm{R}^{\mathrm{na}}_{1/3} \ge N/3$. Together with $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = N$ this pins the value, and no part of the open $\mathrm{R}$ exponent is needed.
Kushilevitz's function (iterated) total \(\Theta(N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with both ends $N$ here.
Rubinstein's function total \(\Theta(N)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{fbs}(f) = \Theta(N)$ and $\mathrm{D}^{\mathrm{na}}(f) = N$ here.
Ambainis-Sun function total \(\Theta(N)\) Sandwiched: $\mathrm{fbs} \le \mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = N$, with $\mathrm{fbs} = \Theta(N)$ here.
AND composed with NOT-EXACT-HALF total \(\Theta(N)\) Sandwiched: $\mathrm{fbs}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{fbs} = \Theta(n^2)$ and $\mathrm{D}^{\mathrm{na}} = n^2$ here.
Meiburg's tournament-subcube function total \(\ge 14011^{\,d}\) putative $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Omega(\mathrm{bs})$.
Pointer functions total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Variant $f_{2m,m}$: $\mathrm{R}\le\mathrm{R}^{\mathrm{na}}\le\mathrm{D}^{\mathrm{na}}=\widetilde\Theta(n)$, with $\mathrm{R}\ge\mathrm{fbs}=\widetilde\Omega(\sqrt n)$. Nonadaptivity is expected to cost the full input length here, since the whole point of the pointer payload is that queries must chase a chain.
Cheat-sheet functions total \(\widetilde\Omega(n)\) Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\widetilde\Omega(n)$. The ceiling is the cheat-sheet input length $n^{10+o(1)}$, which is not comparable to the other entries in this scale.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3})\) Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\widetilde\Omega(n^{4/3})$.
Gilmer-Saks-Srinivasan functions total \(\Theta(n^2)\) Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\Omega(n^2)$; the ceiling is $\mathrm{D}^{\mathrm{na}}=n^2$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n)\) Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\widetilde\Omega(\sqrt n)$; the ceiling is $\mathrm{D}^{\mathrm{na}}=\widetilde\Theta(n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{2/3})\) Squeeze: $\mathrm{R}^{\mathrm{na}}\ge\mathrm{R}=\widetilde\Omega(n^{2/3})$.
Ambainis' exact-quantum function total \(3^d\) Squeeze: $\mathrm{R}\le\mathrm{Rna}\le\mathrm{Dna}$.
FORRELATION partial \(\widetilde\Theta(\sqrt n)\)· putative The $O(\sqrt n)$ algorithm samples coordinates of $x$ and $y$ from its coins and forms an estimator of $\langle\hat x, y\rangle$, so it is non-adaptive; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \widetilde\Theta(\sqrt n)$.
k-FORRELATION partial \(\widetilde\Theta\!\big(n^{1-1/k}\big)\)· putative The randomized upper bound is an estimator built from coordinates sampled from the coins alone, so it is non-adaptive; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R}$. Adaptivity buys nothing here, exactly as for \(\mathrm{forr}\).
Simon's problem partial \(\Theta(2^{n/2})\) putative Sampling $O(2^{n/2})$ uniformly random points is non-adaptive, and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Theta(2^{n/2})$.
Deutsch-Jozsa partial \(\Theta(1)\) putative Read $10$ fixed positions and answer "balanced" iff they are not all equal; a balanced input fools this with probability $2^{-9}$.
Bernstein-Vazirani partial \(\Theta(n)\) putative Same non-adaptive algorithm; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R}$.
Marked bit partial \(\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$.
Dense marked bit partial \(\Theta(1)\) putative Query both bits of $10$ uniformly random cells and answer from any mark found. All ten miss with probability $\le 2^{-10}$, and the queries are chosen before any answer is seen.
Unstructured search (relation) relation \(\Theta(n)\) Sandwiched between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$.
FIND-1 under a density promise relation \(\Theta(1)\) putative Sampling is already non-adaptive: read $10$ uniformly random positions and output any that is $1$.
Approximate Hamming weight relation \(\Theta(1)\) putative Uniform sampling is non-adaptive.
Correlated-string search relation \(\Theta(\sqrt n)\) putative The algorithm above never looks at an answer before choosing the next query, so it is non-adaptive; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Omega(\sqrt n)$.
SearchCNF relation \(\Theta(1)\)· putative Sampling a clause of $\varphi$ at random and reading its $k$ variables is non-adaptive; for a random $\Delta$-dense $\varphi$ a constant fraction of clauses is falsified by any fixed assignment, so $O(1)$ tries suffice.
Gap-Majority partial \(\Theta(\min(n, 1/\delta^2))\) Sampling is non-adaptive, and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R}$.
Gap-Majority at constant gap partial \(\Theta(1)\) Sampling is non-adaptive.
Parity-labelled FIND-1 partial \(\Theta(1)\) putative Sampling needs no adaptivity: read $10$ uniformly random positions and answer from any that is $1$. A position is $1$ with probability $1/4$, so this fails with probability $(3/4)^{10} < 0.06$.
Approximate index partial \(\Theta(\sqrt{k\log k})\) putative Same remark: the randomized algorithm reads a fixed prefix of $a$ and one array cell chosen from the coins alone, so it is non-adaptive; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R}$.
Collision problem partial \(\Theta(\sqrt n)\) putative Sampling $c\sqrt n$ positions is non-adaptive and finds a collision with constant probability; and $\mathrm{R}^{\mathrm{na}} \ge \mathrm{R} = \Theta(\sqrt n)$. Adaptivity is worth nothing here.
Element distinctness total \(\Theta(n)\) Sandwiched between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$.
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) Between $\mathrm{R} = \Omega(n^{1/3})$ and $\mathrm{D}^{\mathrm{na}} = O(n)$.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{R}$.
Yamakawa-Zhandry problem relation \(2^{\Omega(n)}\) At least $\mathrm{R}$.
Surjectivity total \(\Theta(n)\) Sandwiched: $\mathrm{R}(f) \le \mathrm{R}^{\mathrm{na}}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$ here.
$k$-distinctness total \(\Theta(n)\) Sandwiched between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$.
Triangle finding total \(\Theta(m^2) = \Theta(n)\) Sandwiched between $\mathrm{R} = \Theta(m^2)$ and $\mathrm{D}^{\mathrm{na}} = \binom m2$.
Recursive Fourier sampling partial \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) Sandwiched: $\mathrm{R}_{\varepsilon}(f) \le \mathrm{R}^{\mathrm{na}}_{\varepsilon}(f) \le \mathrm{D}^{\mathrm{na}}(f)$, with $\mathrm{R} = n^{\Omega(\log n)}$ and $\mathrm{D}^{\mathrm{na}} = O(n^{\ell})$ here, so at $\ell = \log n$ the two ends meet at $n^{\Theta(\log n)}$.
Welded trees relation \(\Theta(4^n)\) putative Randomness does not help the non-adaptive algorithm either, so $\mathrm{R}^{\mathrm{na}}/\mathrm{R} = \tilde\Theta(2^{3n/2})$ as well. Upper: $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = \Theta(4^n)$. Lower: let the algorithm draw a random name set $S$, $|S| = t$. Since $\pi$ is a uniformly random injection with only $\pi(\mathrm{ENTRANCE})$ pinned, the exit and its two neighbours land in $S$ with probability at most $3t/(2^{2n}-1)$; conditioned on missing all three, the transcript is independent of which unqueried unused name carries the exit, and there are $2^{2n} - t - 2^{n+2}$ candidates. So the success probability is at most $3t/(2^{2n}-1) + o(1)$, and $t = \Omega(4^n)$ is needed for $2/3$.
Local search on the hypercube relation \(\Theta(2^n)\) putative Randomness buys nothing without adaptivity, and the gap against $\mathrm{R} = \Theta(2^{n/2}\sqrt n)$ is quadratic. Upper: $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = 2^n$. Lower: pick $u$ uniformly and let $f$ be the Hamming distance to $u$ except at $u$ itself, where $f(u) \in \{0, 2n\}$ with a fair coin. Both completions are legal, the reading on any cell other than $u$ is identical, and the valid outputs are disjoint -- $\{u\}$ in one case, the $n$ neighbours of $u$ in the other. A fixed query set $S$ of size $t$ contains $u$ with probability $t/2^n$, so the success probability is at most $t/2^n + 1/2$ and $t \ge 2^n/6$.
Local search on the grid relation \(\Theta(k^d)\) putative Every cell, even with randomness, so $\mathrm{R}^{\mathrm{na}} = \Theta(\mathrm{D}^{\mathrm{na}}) = \Theta(N)$. Randomise the \(\mathrm{D}^{\mathrm{na}}(f)\) construction: draw $u$ uniformly from $[k]^d$, let $f$ be the $\ell_1$ distance to $u$ off $u$, and set $f(u) \in \{0, 2dk\}$ by a fair coin. The two completions have disjoint solution sets and agree everywhere but $u$, so a fixed query set of size $t$ succeeds with probability at most $t/k^d + 1/2$.
Fourier fishing relation \(\Omega(N/\log N),\ O(N)\) Sandwiched between $\mathrm{R}_{\varepsilon} = \Omega(N/\log N)$ and $\mathrm{D}^{\mathrm{na}} = N$.
Ordered search partial \(\Theta(n)\) putative Randomness does not rescue non-adaptivity. Take $k$ uniform on $\{0,\dots,n\}$; a fixed query set of size $t$ leaves the parity determined only when the gap containing $k$ is a singleton, and there are at most $t+1$ singleton gaps, so the algorithm is right with probability at most $\tfrac{t+1}{n+1} + \tfrac12\big(1-\tfrac{t+1}{n+1}\big)$. Forcing this to $\ge 2/3$ gives $t \ge \tfrac{n+1}{3}-1$. Upper: $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = n$.
Tseitin search on an expander relation \(\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $\mathrm{D}^{\mathrm{na}} = n$.
Inner product mod 2 total \(\Theta(n)\) Between $\mathrm{R} = \Theta(n)$ and $n$.
Minsky-Papert one-in-a-box total \(\Theta(m^3) = \Theta(N)\) Between $\mathrm{R} = \Theta(N)$ and $\mathrm{D}^{\mathrm{na}} = N$.
Sink of a tournament total \(\Theta(m^2) = \Theta(N)\) putative Non-adaptively you must read essentially the whole tournament, a full quadratic above $\mathrm{R} = \Theta(\sqrt N)$. Hard distribution: pick $v$ and $u \ne v$ uniformly, orient every edge into $v$ and the rest of the tournament uniformly at random, then flip the edge $uv$ with probability $1/2$. Flipping it destroys the sink and creates a new one only if $u$ is a sink of the sub-tournament, which happens with probability $2^{-(m-2)}$. The unordered pair $\{u,v\}$ is uniform over all $\binom m2$ edges, and flipping the coin is an involution that leaves $x|_S$ unchanged whenever $uv \notin S$, so any fixed $S$ errs with probability $\ge \tfrac12(1 - |S|/\binom m2) - 2^{-(m-2)}$. Hence $|S| = \Omega(N)$, and $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = N$.
Scorpion graphs total \(\Theta(m^2) = \Theta(N)\) putative Non-adaptively the scorpion property is evasive up to a constant, a full quadratic above $\mathrm{R} = \Theta(\sqrt N)$. Hard distribution: draw an ordered triple $(s,t,b)$ uniformly and the foot subgraph uniformly, giving a scorpion $G$, then delete the edge $st$ with probability $\tfrac12$ (which isolates $s$, so the result is never a scorpion). Flipping that coin is a measure-preserving involution that does not change $x|_S$ whenever $st \notin S$, so given $x|_S$ the answer is an unbiased coin on that event; since $\{s,t\}$ is uniform over all $\binom m2$ pairs, a fixed $S$ succeeds with probability at most $1 - \tfrac12(1 - |S|/\binom m2)$, forcing $|S| \ge \binom m2/3$. Upper: $\mathrm{R}^{\mathrm{na}} \le \mathrm{D}^{\mathrm{na}} = N$.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) Sandwiched between $\mathrm{R} = \Theta(N)$ and $\mathrm{D}^{\mathrm{na}} = N$.