Minimum certificate complexity
Min (rather than max) over inputs of the smallest certificate.
Definition
$\mathrm{C}_{\min}(f) = \min_x \mathrm{C}_x(f)$. Appears in the study of "every function has a short certificate somewhere" and in the $\mathrm{UC}_{\min}$ variant used by Ben-David-Hatami-Tal.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{C}_{\min}(f)\). “\(\mathrm{C}_{\min}(f)\) in terms of it” is the pair with \(\mathrm{C}_{\min}(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 | \(1\) | Any $1$-input is certified by a single $1$. |
| AND total | \(1\) | Any $0$-input is certified by a single $0$. |
| PARITY total | \(n\) | Every input needs the whole assignment; PARITY is evasive in the strongest sense. |
| MAJORITY total | \((n+1)/2\) | Every input needs a full majority-sized certificate, so the min and the max coincide. |
| Threshold total | \(\min\{k,\; n-k+1\}\) putative | A $1$-input needs $k$ ones exhibited and a $0$-input needs $n-k+1$ zeros, so $\mathrm{C}(x)$ takes exactly the two values $k$ and $n-k+1$; the minimum over inputs is the smaller of them. Contrast $\mathrm{C} = \max\{k,\;n-k+1\}$: the gap between \(\mathrm{C}_{\min}(f)\) and \(\mathrm{C}(f)\) on this one family is already unbounded (take $k=1$). |
| Symmetric functions (general) total | \(\min_j\,(\ell_j + n - r_j)\) putative | The same per-input formula as the \(\mathrm{C}^1(f)\) line, minimised rather than maximised over all weights $j$. Equivalently $n$ minus the length of the longest constancy interval of the slice pattern, plus one. Checks: $\vee_n$ gives $1$, $\mathrm{THR}^n_k$ gives $\min\{k,\ n-k+1\}$, $\oplus_n$ gives $n$. |
| EXACT-HALF total | \(n/2 + 1\) putative | Every $0$-input costs $n/2+1$ and every $1$-input costs $n$, so the minimum is the $0$-side value. The factor-$2$ gap to $\mathrm{C} = n$ is the whole of the asymmetry of $\mathrm{EH}$. |
| ODD-MAX-BIT total | \(1\) putative | At $x = e_n$, reading $x_n = 1$ already decides (the answer is the parity of $n$). Certificate complexity varies by a factor of $\Theta(n)$ across inputs. |
| ADDRESS / multiplexer total | \(k+1\) putative | A certificate that fixes $j$ of the address bits leaves $2^{k-j}$ live addresses and must therefore pin all $2^{k-j}$ of the corresponding table entries, for a total of $j + 2^{k-j} \ge k+1$ coordinates, with equality only at $j=k$ (and $j=k-1$). So every input has $\mathrm{C}(x) = k+1$: $\mathrm{C} = \mathrm{C}_{\min} = k+1$ and $\mathrm{ADDR}$ is perfectly balanced in certificate size. |
| Binary tree navigation total | \(k\) putative | Every input has the same certificate structure. |
| TRIBES total | \(\Theta(\log n)\) | The cheapest input to certify is a $1$-input: one satisfied tribe, $w=\Theta(\log n)$ bits. |
| AND-OR tree (depth 2) total | \(n\) putative | Certifying a $1$ needs a witness in each of the $n$ blocks; certifying a $0$ needs a whole empty block, $n$ bits. So every input costs exactly $n$: $\mathrm{C} = \mathrm{C}_{\min} = n$. |
| NAND tree (balanced AND-OR formula) total | \(\Theta(\sqrt N)\) putative | A minimal certificate takes one child at every $0$-forcing gate and both children at every $1$-forcing gate (or vice versa), so it has $2^{\lceil d/2\rceil}$ or $2^{\lfloor d/2 \rfloor}$ leaves -- $\Theta(\sqrt N)$ either way. Every input of the balanced NAND tree costs the same up to $\sqrt2$: $\mathrm{C} = \Theta(\mathrm{C}_{\min})$. |
| Recursive MAJORITY-of-3 total | \(2^d\) putative | Every input of $\mathrm{MAJ}_3$ costs exactly $2$ to certify, so certificate complexity is the same at every input at every level: $\mathrm{C}_{\min} = \mathrm{C} = 2^d$. Recursive majority is perfectly homogeneous in this respect, unlike \(K^{\circ k}\) ($\mathrm{C}_{\min} = \mathrm{C}^{0.77}$). |
| Kushilevitz's function (iterated) total | \(4^k = N^{0.7737}\) putative | Exhaustive search over the $64$ inputs of the base function gives $\mathrm{C}_{\min}(K)=4$, attained on both sides ($\min_{K(x)=0}\mathrm{C}_x = \min_{K(x)=1}\mathrm{C}_x = 4$). Minimum certificate complexity composes: a certificate of $f\circ g^n$ at $x$ restricts to a certificate of $f$ at $g(x)$ on the blocks it certifies, so $\mathrm{C}_x(f\circ g^n) = \min_{S}\sum_{j\in S}\mathrm{C}_{x^j}(g)$ over certificates $S$ of $f$, and since $K$ is $4$ on both sides the minimum is $4\cdot\mathrm{C}_{\min}$ of the previous level. So $\mathrm{C}_{\min} = 4^k$ against $\mathrm{C} = 6^k$ -- a genuine gap, unlike \(\mathrm{AND}_n \circ \mathrm{OR}_n\) where the two coincide. |
| Rubinstein's function total | \(n = \sqrt N\) putative | The cheapest inputs are the $1$-inputs, at cost $\mathrm{C}^1 = n$; a $0$-input costs at least $2n$, since each of the $n$ blocks needs at least $\mathrm{C}_{\min}(g) = 2$ bits. So $\mathrm{C}_{\min} = \sqrt N$ against $\mathrm{C} = N/2$. |
| Ambainis-Sun function total | \(3k+2\) putative | The $1$-inputs are the cheap ones: $\mathrm{C}_{\min} = \mathrm{C}^1 = 3k+2 = \Theta(\sqrt N)$. |
| AND composed with NOT-EXACT-HALF total | \(n = \sqrt N\) putative | The $0$-inputs are far cheaper to certify than the $1$-inputs: $\mathrm{C}_{\min} = \mathrm{C}^0 = n = \sqrt N$ against $\mathrm{C} = \Theta(N)$. |
| Meiburg's tournament-subcube function total | \(\le 7149\cdot 14011^{\,d-1}\) putative | $\mathrm{C}_{\min} = \min\{\mathrm{C}^0,\mathrm{C}^1\} = \mathrm{C}^1$ here, since the \(\mathrm{C}^1(f)\) bound $7149\cdot 14011^{\,d-1} \approx 0.51\cdot 14011^{\,d}$ is strictly below the exact $\mathrm{C}^0 = 14011^{\,d}$. The relation $\mathrm{D} \le \mathrm{C}_{\min}\cdot\mathrm{C}$ therefore gives only $\mathrm{D} = O(14011^{2d})$, far above the recorded lower bound. |
| Pointer functions total | \(\widetilde\Theta(\sqrt n)\) putative | Variant $f_{2m,m}$, a $2m\times m$ grid with $n=\widetilde\Theta(m^2)$ bits. Upper: $\mathrm{C}_{\min}\le\mathrm{C}=\widetilde O(\sqrt n)$. Lower: certifying a $1$ requires exhibiting a whole marked column, i.e. all $2m$ cells of it; certifying a $0$ requires an unmarked cell in each of the $m$ columns. So $\mathrm{C}_x\ge m=\widetilde\Omega(\sqrt n)$ for every input $x$, not just the worst one. |
| Cheat-sheet functions total | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{C}_{\min}\le\mathrm{C}=\widetilde O(\sqrt n)$. No matching lower bound is claimed -- a single cheaply certified input would not disturb anything above. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde O(n)\) | Squeeze: $\mathrm{C}_{\min}\le\mathrm{C}^1\le\mathrm{UC}_1=\widetilde O(n)$ -- every $1$-input is cheap to certify, and the hardness lives entirely on the $0$-side. |
| Gilmer-Saks-Srinivasan functions total | \(n\) putative | Upper: $\mathrm{C}_{\min}\le\mathrm{C}^1=n$. Lower: a $1$-certificate must pin a whole isolated point of some copy ($n$ bits), and a $0$-certificate must force all $n$ copies to $0$ at $\ge n/100$ bits each; so $\mathrm{C}_x\ge n$ for every input. |
| Random-indicator gadget total | \(\Theta(n)\) putative | Floor: every $0$-input needs $n/100$ bits and every $1$-input needs $n$, so the minimum certificate complexity is already linear -- unusually, $\mathrm{C}_{\min}=\Theta(\mathrm{C})$ here. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Theta(\sqrt n)\) putative | Upper: $\mathrm{C}_{\min}\le\mathrm{C}^1=\widetilde O(\sqrt n)$. Lower: a $1$-certificate must exhibit all $k$ cells of a witness column plus the pointer check, so $\mathrm{C}_x=\widetilde\Omega(\sqrt n)$ at every $1$-input, and $0$-inputs cost $\widetilde\Theta(n)$. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Theta(n^{1/3})\) putative | Upper: $\mathrm{C}_{\min}\le\mathrm{C}^1=\widetilde O(n^{1/3})$. Lower: certifying a $1$ requires the whole witness column and its list, $\widetilde\Omega(n^{1/3})$ bits, and every $0$-input costs at least that much too. |
| Ambainis' exact-quantum function total | \(\Theta(2.3028^d)\) putative | Exact recursion. Let $a_d=\min_{x\in f^{-1}(0)}\mathrm{C}_x$ and $b_d=\min_{x\in f^{-1}(1)}\mathrm{C}_x$. A $0$-certificate must pin all three children (they must be shown equal): $a_d=3\min\{a_{d-1},b_{d-1}\}$. A $1$-certificate need only exhibit two children with different values: $b_d=a_{d-1}+b_{d-1}$. With $a_0=b_0=1$ one gets $b_d<a_d$ for all $d\ge1$, hence $a_d=3b_{d-1}$ and $b_d=b_{d-1}+3b_{d-2}$, i.e. $1,2,5,11,26,59,137,\dots$, whose growth rate is the root $(1+\sqrt{13})/2=2.3027\ldots$ So $\mathrm{C}_{\min}=\Theta(2.3028^d)=\Theta(n^{0.7587})$, strictly between $\lambda=n^{1/2}$ and $\mathrm{C}=n$. |
| FORRELATION partial | \(\Theta(n)\)· putative | Every certificate, at every promise input, fixes $\Omega(n)$ coordinates. Suppose one fixes fewer than $10^{-3}n$; then at least $0.999n$ coordinates of $x$ and $0.999n$ of $y$ are free, and by Cauchy--Schwarz the fixed $y$-positions carry $\sum_{\text{fixed } j}|\hat x_j| \le \sqrt{10^{-3}n} \le 0.032\sqrt n$. At a $1$-input, $\Phi \ge 3/5$ forces $\sum_j |\hat x_j| \ge 0.6\sqrt n$; setting every free $y_j$ to $-\mathrm{sign}(\hat x_j)$ drives $\Phi$ below $-0.5$, and reverting those bits one at a time back to their original values moves $\Phi$ in steps of $2|\hat x_j|/\sqrt n \le 2/\sqrt n < 1/50$ up to $\Phi \ge 3/5$, so some intermediate assignment has $|\Phi| \le 1/100$ -- a $0$-input consistent with the certificate. At a $0$-input, set the free $x$-coordinates uniformly at random: then $\sum_j |\hat x_j| \ge 0.7\sqrt n$ with high probability, and setting every free $y_j$ to $\mathrm{sign}(\hat x_j)$ gives $\Phi \ge 0.7 - 2(0.032) > 3/5$, a $1$-input consistent with the certificate. Either way the set was not a certificate. With $\mathrm{C}_{\min} \le \mathrm{C} \le 2n$ this pins $\Theta(n)$. |
| k-FORRELATION partial | \(O(kn)\) | At most $\mathrm{C}$. |
| Simon's problem partial | \(2\) putative | On a two-to-one input, one colliding pair. |
| Deutsch-Jozsa partial | \(2\) putative | Attained on the balanced inputs. |
| Bernstein-Vazirani partial | \(n\) putative | See $\mathrm{C}$: the spanning requirement is input-independent. |
| Unique search partial | \(1\) | Attained at the $1$-inputs. |
| Two-or-none search partial | \(1\) putative | A single literal $x_i = 1$ already forces $f = 1$, because weight $1$ is off the promise. |
| Marked bit partial | \(1\) putative | Equal to $\mathrm{C}$: the same one-query certificate works everywhere. |
| Dense marked bit partial | \(1\) | Every input has a $1$-query certificate. |
| Unstructured search (relation) relation | \(1\) putative | At any input with a $1$, that single queried bit certifies its own index. The $n$ in $\mathrm{C}$ comes only from $0^n$, so $\mathrm{C}/\mathrm{C}_{\min} = n$. |
| FIND-1 under a density promise relation | \(1\) putative | Equal to $\mathrm{C}$: the same one-bit certificate works at every input, since the promise guarantees a $1$ exists. |
| Approximate Hamming weight relation | \(\Theta(n)\) putative | Equal to $\mathrm{C}$: the counting argument there -- a partial assignment fixing $q$ coordinates leaves $|x|$ free in a window of width $n-q$ -- is input-independent, so every input needs $(1-2\varepsilon)n$ fixed coordinates. Certificate-uniform hardness is what drives the $\mathrm{R}_0$ and $\mathrm{DTsize}$ bounds above. |
| Correlated-string search relation | \(\Theta(n)\) putative | The count above is input-independent, so $\mathrm{C}_{\min} = \mathrm{C} = \Theta(n)$. |
| SearchCNF relation | \(\Theta(1)\) | Between $1$ and $\mathrm{C} = \Theta(1)$: the short certificate is available at every assignment, which is exactly why $\mathrm{R}$ and $\mathrm{cbs}$ stay constant while $\mathrm{D} = \Theta(n)$. |
| Gap-Majority partial | \(\Theta(n)\) | Every certificate on either side has $n/2-\delta n+1$ coordinates, so the min over inputs equals the max: $\mathrm{C}_{\min} = \mathrm{C} = \mathrm{D}$ up to $\pm 1$. |
| Gap-Majority at constant gap partial | \(\Theta(n)\) | Every certificate has the same length, so the min over inputs equals the max. |
| Parity-labelled FIND-1 partial | \(1\) putative | Equal to $\mathrm{C}$: every input has $n/4$ one-bit certificates, so the min over inputs and the max coincide. |
| Approximate index partial | \(\Theta(1)\) putative | See $\mathrm{C}$: the same certificate works at every input, so $\mathrm{C}_{\min} = \mathrm{C} = \Theta(1)$. |
| Collision problem partial | \(2\) putative | A colliding pair, on the two-to-one side. |
| Element distinctness total | \(2\) putative | A repeated pair. |
| Ambainis-Belovs function partial | \(O(n)\) | At most $\mathrm{C} = O(n)$, i.e. $\min\{\mathrm{C}^0,\mathrm{C}^1\} \le O(n)$. |
| Ben-David-Kundu total search problems relation | \(\Theta(\log^6 n)\) putative | Unusually, the min and the max coincide. Any certificate must name an output $(i_1,\dots,i_t)$ and a shift, and to know that $i_\ell$ is an all-$1$ block of $x^\ell \oplus h$ one must have read all $\log(n/2)$ bits of that block, for every $\ell$. So $\mathrm{C}_x \ge t\log(n/2)$ on every input, matching the upper bound of the \(\mathrm{C}(f)\) entry. |
| Yamakawa-Zhandry problem relation | \(n\) putative | Every input has the same $n$-bit certificate shape, so the minimum over inputs equals the maximum. |
| Surjectivity total | \(\Theta(n/\log n)\) putative | Upper: $\mathrm{C}_{\min} \le \mathrm{C}^0 = N$. Lower: in any certificate at most $R-1$ slots can be left entirely unfixed -- $R$ free slots could be set to $1,\dots,R$ and make the input surjective -- so every certificate touches at least $N-R+1 = R+1$ slots, and $\mathrm{C}_{\min} \ge R+1 = \Theta(N)$. The $1$-side is more expensive ($\mathrm{C}^1 = n/2$), so the minimum is attained on $0$-inputs. |
| $k$-distinctness total | \(k\) putative | The cheapest certificate anywhere is a $k$-fold repeat; every $0$-input costs $n$. |
| Triangle finding total | \(3\) putative | A $1$-certificate is a triangle and cannot be smaller; every $0$-input costs $\binom m2$. |
| Welded trees relation | \(\Theta(1)\) | $1\le\mathrm{C}_{\min}\le\mathrm{C}=\Theta(1)$: nine queries exhibit the EXIT vertex and certify it at every input, so the cheapest input is no cheaper than a constant. |
| Local search on the hypercube relation | \(n+1\) | Exactly $n+1$, like $\mathrm{C}$: certifying that a vertex is a local minimum means reading it and all $n$ neighbours, and that cost is the same at every input, so the min over inputs equals the max. |
| Local search on the grid relation | \(\Theta(1)\) | Between $d+1$ and $\mathrm{C}=2d+1$: a corner cell has only $d$ neighbours to check, an interior cell has $2d$, and $d$ is a constant. |
| Fourier fishing relation | \(\Theta(N)\) putative | Not just the worst input: every input is expensive. Certifying the answer $z$ means forcing $|\sum_x f(x)(-1)^{x\cdot z}|\ge\sqrt N$, and the unread cells can contribute $-(N-|S|)$ to that sum, so a certificate of size $|S|$ forces nothing unless $|S|\ge(N+\sqrt N)/2$. Hence $\mathrm{C}_{\min}\ge N/2$, matching $\mathrm{C}=\Theta(N)$. |
| Ordered search partial | \(1\) putative | At the two extreme inputs $0^n$ and $1^n$ a single query at the relevant end suffices, since only one promise input is consistent with it. |
| Tseitin search on an expander relation | \(\Theta(1)\) putative | At most $\mathrm{C} = O(1)$, at least $1$. |
| Inner product mod 2 total | \(n/2\) putative | A certificate must kill every term $x_iy_i$: for each $i$ it must fix $x_i=0$, or $y_i=0$, or both $x_i=y_i=1$. So $\mathrm{C}(x,y) = m + |x \wedge y|$ exactly. The minimum is $m = n/2$, attained at every input with $x \wedge y = 0$ (e.g. $x = 0^m$), and the maximum is $2m = n$ at $x=y=1^m$ -- which is where the recorded $\mathrm{C} = n$ comes from. |
| Minsky-Papert one-in-a-box total | \(m = N^{1/3}\) putative | Every $1$-input costs exactly $m$ (one witness per box) and every $0$-input costs exactly $m^2$ (a whole empty box), so the minimum is the $1$-side: $\mathrm{C}_{\min} = m$ against $\mathrm{C} = m^2$. |
| Sink of a tournament total | \(m-1\) putative | The cheapest inputs are the $1$-inputs, at $\mathrm{C}^1 = m-1$; every $0$-input costs $m$. So certificate complexity is essentially constant across SINK's domain, in sharp contrast to its sensitivity, which swings from $3$ to $m-1$. |
| Scorpion graphs total | \(m-1\) putative | Upper: at the empty graph, fixing the $m-1$ pairs at one vertex to absent isolates it, and a scorpion has no isolated vertex (the body dominates everything but the sting, and the sting has degree $1$). Lower: if a set $S$ of $|S| = k$ pairs leaves three vertices untouched, take them as $(s,t,b)$ -- every pair the triple touches is then free, and the feet may do anything -- so the subcube contains a scorpion and $S$ is not a $0$-certificate; hence $m - 2k \le 2$, i.e. every $0$-input costs at least $(m-2)/2$. Every $1$-input costs $\mathrm{C}^1 = 3m-6$. Exhaustive search gives $\mathrm{C}_{\min} = m-1$ exactly for $4 \le m \le 6$, attained only at graphs with an isolated vertex. |
| Graph connectivity total | \(m-1\) putative | Both kinds of certificate need $m-1$ coordinates and both achieve it: a spanning tree on the connected side, an isolated vertex on the disconnected side. So $\mathrm{C}_{\min} = \Theta(\sqrt{\mathrm{C}})$ -- connectivity is one of the cleanest natural examples of certificate complexity that varies quadratically across inputs. |