0-certificate complexity
Largest minimal certificate over 0-inputs; the co-nondeterministic query complexity.
also written:
co-nondeterministic query complexity, C_0
Definition
$\mathrm{C}^0(f) = \max_{x \in f^{-1}(0)} \mathrm{C}_x(f)$: the number of queries a nondeterministic algorithm needs to certify that $f(x) = 0$. Note the notation clash in the literature: some papers write $\mathrm{C}_0$ for this, others use $C^{(0)}$.
Basic facts
- $\mathrm{D}(f) \le \mathrm{C}^0(f)\,\mathrm{C}^1(f)$; this is tight for $\mathrm{AND}\circ\mathrm{OR}$.
- $\mathrm{C}(f) = \max(\mathrm{C}^0(f),\mathrm{C}^1(f))$.
- $\mathrm{C}^0(f) = \mathrm{C}^1(\bar f)$.
- $\mathrm{ndeg}(f) \le \mathrm{C}^1(f)$ and $\mathrm{rdeg}(f) \le \mathrm{C}(f)$.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{C}^0(f)\). “\(\mathrm{C}^0(f)\) in terms of it” is the pair with \(\mathrm{C}^0(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 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| OR total | \(n\) | |
| AND total | \(1\) | |
| PARITY total | \(n\) | |
| MAJORITY total | \((n+1)/2\) | |
| Threshold total | \(n-k+1\) | |
| Symmetric functions (general) total | \(\max\{\,\ell_j + n - r_j \;:\; f_j = 0\,\}\) putative | Same computation as the \(\mathrm{C}^1(f)\) line, maximised over $0$-inputs: with $[\ell_j, r_j]$ the maximal constancy interval of the slice pattern around $j$, a minimum certificate at weight $j$ costs $\ell_j$ ones plus $n - r_j$ zeros. Checks: $\vee_n$ gives $n$, $\mathrm{THR}^n_k$ gives $n-k+1$, \(\mathrm{EH}_n\) gives $n/2+1$. |
| EXACT-HALF total | \(n/2 + 1\) putative | A partial assignment with $a$ ones and $b$ zeros forces the answer $0$ exactly when $a > n/2$ or $b > n/2$, so the cheapest $0$-certificate exhibits $n/2+1$ equal bits, and every $0$-input has one. Matches $\mathrm{s}^0 = n/2+1$, so blocks and fractional relaxations buy nothing on the $0$-side. |
| ODD-MAX-BIT total | \(\lceil n/2 \rceil\) putative | Attained at $0^n$, where zeroing the $\lceil n/2\rceil$ odd positions already forces the answer $0$ -- and at any $0$-input whose highest $1$ sits at position $2$. |
| ADDRESS / multiplexer total | \(k+1\) | |
| Binary tree navigation total | \(k\) putative | As $\mathrm{C}$: complementing the bottom level swaps the two sides, so the certificate structure is the same for both. (Verified exhaustively for $k \le 3$.) |
| TRIBES total | \(\Theta(n/\log n)\) | |
| AND-OR tree (depth 2) total | \(n\) | |
| NAND tree (balanced AND-OR formula) total | \(2^{\lceil d/2\rceil} = \Theta(\sqrt N)\) putative | Certifying $f_d = 0$ means certifying both children to be $1$, and certifying $f_d = 1$ means certifying one child to be $0$: $\mathrm{C}^0(f_d) = 2\,\mathrm{C}^1(f_{d-1})$ and $\mathrm{C}^1(f_d) = \mathrm{C}^0(f_{d-1})$, from $\mathrm{C}^0(f_0) = \mathrm{C}^1(f_0) = 1$. So the two sides differ by exactly a factor $\sqrt2$ when $d$ is odd and agree when $d$ is even. |
| Recursive MAJORITY-of-3 total | \(2^d\) | Between $\mathrm{bs}^0 = 2^d$ and $\mathrm{C} = 2^d$. |
| Kushilevitz's function (iterated) total | \(N\) | Between $\mathrm{bs}^0 = N$ and the trivial ceiling $N$. |
| Rubinstein's function total | \(N/2 = n^2/2\) putative | Certifying $0$ means certifying all $n$ blocks silent, and the worst block state is $0^n$, which needs one zero from each of its $n/2$ pairs. So $\mathrm{C}^0(f) = n\cdot\mathrm{C}^0(g) = n^2/2$ and $\mathrm{C} = \mathrm{C}^0 = N/2$. |
| Ambainis-Sun function total | \(6k^2+7k+2\) putative | Certifying $f=0$ means certifying all $3k+2$ blocks silent, and $\mathrm{C}^0(g) = 2k+1$ exactly: from any $0$-input of $g$, naming one coordinate that already violates each of the $2k+1$ patterns is a certificate, and $\mathrm{C}^0(g) \ge \mathrm{bs}^0(g) = 2k+1$. So $\mathrm{C}^0(f) = (3k+2)(2k+1) = \mathrm{bs}^0(f)$: block sensitivity and certificate complexity coincide. (Brute force confirms $\mathrm{C}^0(g) = 3, 5$ at $k = 1,2$.) |
| AND composed with NOT-EXACT-HALF total | \(n = \sqrt N\) putative | To certify $f = 0$ it suffices to pin one block at weight exactly $n/2$, which costs all $n$ of its bits and no fewer. |
| Meiburg's tournament-subcube function total | \(14011^{\,d}\) putative | Exact, and the load-bearing cell for the whole entry. The base function is the indicator of a union of $k = 14011$ subcubes, so a $0$-input is certified by naming, for each subcube, one coordinate on which it is violated: $\mathrm{C}^0 \le 14011$ for $d=1$. Since $\mathrm{C}^1 \le 7149$ (the codimension of a single subcube), $\mathrm{C} = 14011$ at $d=1$, and certificate complexity is submultiplicative under composition ($\mathrm{C}^0(F\circ g^m) \le \mathrm{C}^0(F)\,\mathrm{C}(g)$: certify the outer coordinates, then each of the corresponding inner copies), giving $\mathrm{C}^0 \le 14011^{\,d}$. The matching lower bound is $\mathrm{C}^0 \ge \mathrm{bs}^0 \ge 14011^{\,d}$ (see \(\mathrm{bs}^0(f)\)). Consequently $\mathrm{bs} = \mathrm{fbs} = \mathrm{FC} = \mathrm{EC} = \mathrm{C} = 14011^{\,d}$ exactly, all of them being squeezed between $\mathrm{bs}^0$ and $\mathrm{C}$. Meiburg26 |
| Pointer functions total | \(\widetilde\Theta(\sqrt n)\) putative | Variant $f_{2m,m}$. Upper: $\mathrm{C}^0\le\mathrm{C}=\widetilde O(\sqrt n)$. Lower: $\mathrm{D}\le\mathrm{C}^0\mathrm{C}^1\le\mathrm{C}^0\cdot\mathrm{C}$, and $\mathrm{D}=\widetilde\Omega(n)$ with $\mathrm{C}=\widetilde O(\sqrt n)$ forces $\mathrm{C}^0=\widetilde\Omega(\sqrt n)$. So neither side of the certificate complexity can be the cheap one. |
| Cheat-sheet functions total | \(\widetilde\Theta(\sqrt n)\) putative | Upper: $\mathrm{C}^0\le\mathrm{C}=\widetilde O(\sqrt n)$. Lower: $\mathrm{D}\le\mathrm{C}^0\mathrm{C}^1\le\mathrm{C}^0\cdot\mathrm{C}$ with $\mathrm{D}=\widetilde\Theta(n)$ and $\mathrm{C}=\widetilde O(\sqrt n)$. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Theta(n^2)\) | Lower bound $\Omega(n^2)$ at the all-copies-are-$z$ input [BBGJK21, Claim 16]: a cheaper certificate can neither pin down the $\mathrm{Eah}$-values nor touch every array cell. Upper bound from $\mathrm{C}_0\le\mathrm{D}=\widetilde O(n^2)$. BBGJK21 |
| Gilmer-Saks-Srinivasan functions total | \(\Theta(n^2)\) | A random $g_n$ has $\mathrm{C}_0(g_n)=\Theta(n)$, and $\mathrm{OR}$-composition multiplies the $0$-side by $n$ [GSS16, Prop. 31, Claim 34]. No logarithmic loss anywhere. GSS16 |
| Random-indicator gadget total | \(\Theta(n)\) | Floor $\mathrm{C}^0\ge n/100$ [GSS16, Thm 32]: a $0$-certificate is a subcube of $0$-inputs, and every subcube of codimension $n/100$ contains a planted point. Ceiling: the whole input, $n$. GSS16 |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Theta(n)\) putative | Upper: $\mathrm{C}_0\le\mathrm{D}=\widetilde O(n)$. Lower: take the $0$-input in which every matrix bit is $1$ and each column carries its single pointer in its last cell. A $0$-certificate must refute all $k$ columns; refuting column $j$ means either pinning its pointer chain (all $k$ cells of the column, since "the first cell that has a pointer" is only determined once the earlier cells are fixed to $\bot$) or ruling out $0$-valued targets globally, which means fixing all $k^2$ matrix bits to $1$. Both cost $\Theta(k^2)$ bits $=\widetilde\Theta(n)$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Theta(n^{2/3})\) putative | Upper: $\mathrm{C}_0\le\mathrm{D}=\widetilde O(n^{2/3})$. Lower: take a $0$-input with exactly one all-$1$ column $c$, whose list sits in the last cell of $c$ and has at least one target carrying $1$. Every other column is refuted by a single $0$ bit, but refuting $c$ itself forces the certificate to pin the whole column -- the $k-1$ earlier pointer fields as $\bot$ plus the list itself, $\Theta(k^2\log k)=\widetilde\Theta(n^{2/3})$ bits. Fixing another column entirely to $1$ (the cheap $\Theta(k)$-bit block that works for all other columns) is not available, since no other column is all-$1$ in this input. |
| Ambainis' exact-quantum function total | \(3^d\) | Squeeze: $\mathrm{bs}_0\le\mathrm{C}_0\le n$. Certifying the all-zero input really does require all $3^d$ bits. |
| FORRELATION partial | \(\Theta(n)\) putative | Take the same bent $x$ and $y = \chi_{j_0}$, i.e. $y_j = (-1)^{j\cdot j_0}$. Then $\sum_j \hat x_j y_j = x_{j_0} = \pm1$, so $|\Phi| = 1/\sqrt n \le 1/100$ and this is a $0$-input. Since $\sum_j |\hat x_j| = \sqrt n$ and $\sum_j \hat x_j y_j = \pm 1$, the number of $j$ with $y_j \ne \mathrm{sign}(\hat x_j)$ is $n/2 \pm \sqrt n/2$, and flipping any one of them raises $\Phi$ by exactly $2/n$. Flipping $0.31n$ of them reaches $\Phi \ge 3/5$, so a certificate must fix at least $n/2 - \sqrt n - 0.31n \ge 0.18n$ of the $y$-coordinates. With $\mathrm{C}^0 \le 2n$ this gives $\Theta(n)$. |
| Simon's problem partial | \(\Theta(2^{n/2})\) putative | The injective side. See $\mathrm{C}$: a certificate must exhibit, for every shift $s \ne 0$, a queried pair $x, x\oplus s$ with $g(x) \ne g(x \oplus s)$, and $q$ queried points realise only $\binom q2$ differences. |
| Deutsch-Jozsa partial | \(N/2+1\) putative | Fixing $|S|$ coordinates to $0$ still admits a balanced input whenever $|S| \le N/2$, so a $0$-certificate needs $N/2+1$ zeros -- and that many suffice. |
| Unique search partial | \(n\) | Fixing only $n-1$ coordinates of $0^n$ to $0$ leaves the domain point $e_j$ at the free coordinate $j$, and that is a $1$-input. |
| Two-or-none search partial | \(n-1\) putative | A partial assignment of $n-2$ zeros leaves two free coordinates that may both be $1$, a $1$-input; $n-1$ zeros force the last coordinate to $0$. |
| Marked bit partial | \(1\) putative | See $\mathrm{C}$: a single $0$-mark. |
| Dense marked bit partial | \(1\) putative | See $\mathrm{C}$: a single $0$-mark, i.e. some $z_b = 1$. |
| Unstructured search (relation) relation | \(n\) putative | The distinguished answer $\bot$ is valid only at $0^n$, and certifying it means exhibiting a $0$ in every coordinate. So $\mathrm{C}^0 = n$ while $\mathrm{C}^1 = 1$ -- all of $\mathrm{C} = n$ sits on the $\bot$ side. |
| Gap-Majority partial | \(\Theta(n)\) | Exactly $n/2-\delta n+1$; see $\mathrm{C}$, which is attained on both sides. |
| Gap-Majority at constant gap partial | \(\Theta(n)\) | See $\mathrm{C}$; attained on both sides. |
| Parity-labelled FIND-1 partial | \(1\) putative | See $\mathrm{C}$: a single even-indexed $1$. |
| Approximate index partial | \(\Theta(1)\) putative | See $\mathrm{C}$; the two sides are symmetric. |
| Collision problem partial | \(n/2+1\) putative | The one-to-one side: $n/2$ distinct answers can always be extended to a two-to-one $g$, so nothing short of $n/2+1$ certifies injectivity against the promise. |
| Element distinctness total | \(2\) putative | A colliding pair. This is the lopsided pair of certificate complexities that defeats the positive-weight adversary -- see the \(\mathrm{Adv}(f)\) entry. |
| Ambainis-Belovs function partial | \(O(n)\) | At most $\mathrm{C} = O(n)$. |
| Surjectivity total | \(\Theta(n/\log n)\) putative | Exactly $N$, the number of slots, which at $R = N/2$ is $n/\log_2 R = \Theta(n/\log n)$. Upper: a $0$-input misses some value $u$, and forcing $x_i \ne u$ costs a single bit per slot -- fix one position where $x_i$ and $u$ disagree. Lower: take the $0$-input in which every value except $u$ occurs at least twice; then for each slot $i$ the input obtained by rewriting $x_i$ to $u$ is surjective, so the certificate must fix a bit in every slot. Verified by exhaustive search at $R = 4$, $N = 8$, where $\max_x \mathrm{C}_x = 8 = N$ over all $0$-inputs. (An earlier version of this entry said $n$; that over-counts by a factor $\log R$ -- one does not have to pin down each $x_i$, only to keep it away from $u$.) |
| $k$-distinctness total | \(n\) putative | Take a $0$-input in which one symbol occurs exactly $k-1$ times and everything else is distinct. Leave any other position unread and it could be overwritten with that symbol, completing a $k$-fold repeat; so the certificate must read all $n$ symbols. |
| Triangle finding total | \(\binom m2 = n\) putative | The complete bipartite graph $K_{\lceil m/2\rceil,\lfloor m/2\rfloor}$ is a maximal triangle-free graph, so any unfixed pair could be set to $1$ and create a triangle; a $0$-certificate must fix every variable. |
| Ordered search partial | \(2\) putative | Same two-query certificate; the promise makes both sides equally cheap to certify. |
| Inner product mod 2 total | \(\Theta(n)\) putative | From $\mathrm{C}(x,y) = m + |x\wedge y|$: the top value $n$ needs $x = y = 1^m$, which has $\mathrm{IP} = m \bmod 2$, and the best the other side can do is $|x\wedge y| = m-1$. So $\{\mathrm{C}^0, \mathrm{C}^1\} = \{n,\, n-1\}$, in an order set by the parity of $m$. |
| Minsky-Papert one-in-a-box total | \(m^2 = N^{2/3}\) | A $0$-certificate must exhibit an entirely empty box, and a box has $m^2$ bits. This is the asymmetry the whole function is built on. |
| Sink of a tournament total | \(m\) putative | To rule out every sink you must exhibit an out-edge for every vertex, and an oriented edge is an out-edge for exactly one of its endpoints -- so at least $m$ edges, and $m$ suffice (pick one out-edge per vertex; they are distinct). Note $\mathrm{C}^0 = m > m-1 = \mathrm{C}^1$, so the recorded $\mathrm{C} = \Theta(m)$ is exactly $m$. |
| Scorpion graphs total | \(\Theta(m)\) putative | Upper: $\mathrm{C}^0 \le \mathrm{D} = O(m)$. Lower: at the empty graph, refuting the triple $(\sigma,\tau,\beta)$ needs a queried edge in $\{\sigma\tau\} \cup \mathrm{star}(\beta)\setminus\{\beta\sigma\}$, so a $0$-certificate is a hitting set for that family; unless $P$ meets $\mathrm{star}(\beta)$ twice for nearly every $\beta$ it must contain a near-clique, and $\sum_\beta |P \cap \mathrm{star}(\beta)| = 2|P|$ then forces $|P| = \Omega(m)$; the empty graph's own optimum is exactly $m-1$ (a single star of absent pairs, isolating a vertex) for $5 \le m \le 8$, and that is where $\mathrm{C}_{\min}$ comes from. The maximum over $0$-inputs is larger: exhaustive search gives $\mathrm{C}^0 = 2m-4$ for $4 \le m \le 6$, matching $\mathrm{s}^0$ exactly, so $\mathrm{s}^0 = \mathrm{bs}^0 = \mathrm{C}^0$ and the extremal $0$-input is $K_{m-2}\sqcup K_2$ in all three. |
| Graph connectivity total | \(\Theta(m^2)\) | To certify disconnectedness you must exhibit a cut $(S,\bar S)$ with all $|S|(m-|S|)$ edges absent; the adversary makes $|S| = m/2$, so $\mathrm{C}^0 = \Theta(m^2)$. |
| Ben-David–Kothari championship function total | \(\Omega(n^2)\) | All race lists are spectators and proposal cards are zero. BenDavidKothari26 |
| Ambainis–Iraids–Kokainis unambiguous DNF total | \(\Theta(n^2)\) | Lemma 3.4 and the input-size ceiling. AIK26 |
| Pabbaraju’s optimal unambiguous DNF total | \(\Omega(n^2)\) | Theorem 1. Pabbaraju26 |
| Pabbaraju’s quartic approximate-degree function total | \(\Omega(n^2)\) | All-zero input, equation (42). Pabbaraju26 |