Q The Query Complexity Zoo
\(\mathrm{C}^1(f)\)

1-certificate complexity

Largest minimal certificate over 1-inputs; the nondeterministic query complexity.

also written: nondeterministic query complexity, C_1

Definition

$\mathrm{C}^1(f) = \max_{x \in f^{-1}(1)} \mathrm{C}_x(f)$.

Basic facts

  • $\mathrm{D}(f) \le \mathrm{C}^1(f)\,\mathrm{bs}(f)$ [BBCMdW01, Thm 11].

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{C}^1(f)\). “\(\mathrm{C}^1(f)\) in terms of it” is the pair with \(\mathrm{C}^1(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{C}^1(f)\) in terms of it It in terms of \(\mathrm{C}^1(f)\)
\(\mathrm{C}(f)\) Certificate complexity total1,1 partial1,1 relation1,1 open pair → total∞ partial∞ relation∞ derived open pair →
\(\mathrm{C}^0(f)\) 0-certificate complexity total∞ partial∞ derived open pair → total∞ partial∞ derived open pair →
\(\mathrm{bs}^1(f)\) 1-block sensitivity total∞ partial∞ open pair → total1,? partial1,? derived open pair →
\(\mathrm{ndeg}(f)\) Nondeterministic degree total2,? partial2,? derived open pair → total1,1 partial1,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 \(1\)
AND total \(n\)
PARITY total \(n\)
MAJORITY total \((n+1)/2\)
Threshold total \(k\)
Symmetric functions (general) total \(\max\{\,\ell_j + n - r_j \;:\; f_j = 1\,\}\) putative Exactly. Write $[\ell_j, r_j]$ for the maximal interval of weights containing $j$ on which the slice pattern is constant. A certificate at an input of weight $j$ fixes $a$ ones and $b$ zeros, and the completions have every weight in $[a,\ n-b]$, so it is valid iff $a \ge \ell_j$ and $n-b \le r_j$; both are attainable, since $\ell_j \le j$ ones and $n - r_j \le n-j$ zeros are available. Hence $\mathrm{C}_x = \ell_j + n - r_j$, and $\mathrm{C}^1$ maximises over $1$-inputs. Checks: $\vee_n$ gives $1$, $\mathrm{THR}^n_k$ gives $k$, $\oplus_n$ gives $n$, \(\mathrm{EH}_n\) gives $n$.
EXACT-HALF total \(n\) putative A $1$-input has weight exactly $n/2$, and flipping any single unfixed coordinate leaves the middle slice, so a $1$-certificate must fix all $n$ coordinates. This is the value that makes $\mathrm{C} = n$.
ODD-MAX-BIT total \(\lfloor n/2 \rfloor + 1\) putative Attained at $e_1$: fix $x_1 = 1$ and zero the $\lfloor n/2\rfloor$ even positions above it.
ADDRESS / multiplexer total \(k+1\)
Binary tree navigation total \(k\) putative As $\mathrm{C}^0$.
TRIBES total \(\Theta(\log n)\)
AND-OR tree (depth 2) total \(n\)
NAND tree (balanced AND-OR formula) total \(2^{\lfloor d/2\rfloor} = \Theta(\sqrt N)\) putative See \(\mathrm{C}^0(f)\); the recursion swaps the two sides at every level.
Recursive MAJORITY-of-3 total \(2^d\) Between $\mathrm{bs}^1 = 2^d$ and $\mathrm{C} = 2^d$.
Kushilevitz's function (iterated) total \(N\) Between $\mathrm{bs}^1 = N$ and the trivial ceiling $N$.
Rubinstein's function total \(n = \sqrt N\) putative Certifying $1$ means exhibiting one firing block, and a firing block must be pinned entirely (two ones and $n-2$ zeros): $\mathrm{C}^1(f) = \mathrm{C}^1(g) = n$.
Ambainis-Sun function total \(3k+2\) putative A firing pattern is a $1$-certificate of size $3k+2$, and $\mathrm{C}^1 \ge \mathrm{s}^1 = 3k+2$.
AND composed with NOT-EXACT-HALF total \(n^2/2 + n\) putative To certify $f = 1$ every block must be certified $\ne n/2$, and the cheapest witness for one block exhibits $n/2+1$ equal bits. So $\mathrm{C}^1 = n(n/2+1) = \Theta(N)$, matching the recorded $\mathrm{C}$.
Meiburg's tournament-subcube function total \(\le 7149\cdot 14011^{\,d-1}\) putative A $1$-input of the base function lies in one of the subcubes, whose codimension is $7149$, so $\mathrm{C}^1 \le 7149$ at $d = 1$. Composing, $\mathrm{C}^1(F\circ g^m) \le \mathrm{C}^1(F)\,\mathrm{C}(g)$ -- the outer $1$-certificate fixes both $0$s and $1$s, so the inner cost is the two-sided $\mathrm{C}(g) = 14011^{\,d-1}$. No lower bound is available: nothing in the construction forces a $1$-certificate to be large. Meiburg26
Pointer functions total \(\widetilde\Theta(\sqrt n)\) putative Variant $f_{2m,m}$; the argument of the $\mathrm{C}^0$ line with the roles of the two sides exchanged.
Cheat-sheet functions total \(\widetilde\Theta(\sqrt n)\) putative Same squeeze as the $\mathrm{C}^0$ line with the two sides exchanged; the $1$-certificates are moreover unambiguous, which is what the $\mathrm{UC}_{\min}$ line records.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde O(n)\) Squeeze: $\mathrm{C}_1\le\mathrm{UC}_1=\widetilde O(n)$. The recorded $\mathrm{C}_0$ is quadratically larger -- this is the unambiguous-DNF-vs-CNF-width statement of [BBGJK21, Thm 1], matching the folklore $\mathrm{C}_0\le\mathrm{UC}_1^2$.
Gilmer-Saks-Srinivasan functions total \(n\) putative By [GSS16, Prop. 31] $\mathrm{C}_1(f)=\mathrm{C}_1(g_n)$, and $\mathrm{C}_1(g_n)=n$: the $1$-inputs of $g_n$ are isolated points (pairwise distance $\ge n/100$), so every subcube containing one and no $0$-input is a single point. GSS16
Random-indicator gadget total \(n\) putative The $1$-inputs are isolated (pairwise distance $\ge n/100$), so any subcube containing one and no $0$-input is that single point. GSS16
Goos-Pitassi-Watson partition-number function total \(\widetilde O(\sqrt n)\) The unambiguous decision tree above reads $2k-1 = \widetilde O(\sqrt n)$ cells, so $\mathrm{C}_1\le\mathrm{UC}_1\le\widetilde O(\sqrt n)$. GPW18
Goos-Jayram-Pitassi-Watson function total \(\widetilde O(n^{1/3})\) The unambiguous decision tree costs $\Theta(k\log k)=\widetilde O(n^{1/3})$, so $\mathrm{C}_1\le\mathrm{UC}_1=\widetilde O(n^{1/3})$. GJPW18
Ambainis' exact-quantum function total \(\Theta(3^d)\) putative Certifying $\mathrm{NE}=1$ at the top means exhibiting two children with different values, so $\mathrm{C}_1(\mathrm{NE}^d)=\mathrm{C}_1(\mathrm{NE}^{d-1})+\mathrm{C}_0(\mathrm{NE}^{d-1})=\mathrm{C}_1(\mathrm{NE}^{d-1})+3^{d-1}$, and hence $\mathrm{C}_1(\mathrm{NE}^d)=(3^d+1)/2$. Even the $1$-side of certificate complexity is within a factor $2$ of the input length.
FORRELATION partial \(\Theta(n)\) putative The lower bound recorded under \(\mathrm{C}(f)\) is witnessed at a $1$-input, so $\mathrm{C}^1 = \Theta(n)$ as well.
Simon's problem partial \(2\) putative The two-to-one side: one colliding pair $g(x) = g(y)$, $x \ne y$, already rules out injectivity, and the promise then forces the answer.
Deutsch-Jozsa partial \(2\) putative Every other domain point consistent with "one $0$ here, one $1$ there" is balanced, hence also a $1$-input. Nothing needs to be pinned down beyond killing the two constants.
Unique search partial \(1\) The single literal $x_i = 1$ is satisfied by no other domain point.
Two-or-none search partial \(1\) putative The single literal $x_i = 1$ is consistent with $n-1$ different $1$-inputs, but it already forces the value: weight $1$ is off the promise, so any domain point with $x_i = 1$ has weight $2$.
Marked bit partial \(1\) putative See $\mathrm{C}$: a single $1$-mark.
Dense marked bit partial \(1\) putative See $\mathrm{C}$: a single $1$-mark, i.e. some $y_b = 1$.
Unstructured search (relation) relation \(1\) putative One queried $1$ certifies its own index as a valid output. For a search relation this is the whole of the "yes" side; the $n$ in $\mathrm{C}$ comes entirely from the $\bot$ answer.
FIND-1 under a density promise relation \(1\) putative Same certificate.
Approximate Hamming weight relation \(\Theta(n)\) Same count as $\mathrm{C}$ and $\mathrm{C}_{\min}$: certifying any valid answer needs $(1-2\varepsilon)n$ fixed coordinates, at every input.
SearchCNF relation \(\Theta(1)\) The same $k$-variable certificate as $\mathrm{C}$: reading the variables of a falsified clause certifies that clause as a valid output.
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 odd-indexed $1$.
Approximate index partial \(\Theta(1)\) putative See $\mathrm{C}$; the two sides are symmetric.
Collision problem partial \(2\) putative The two-to-one side: one colliding pair.
Element distinctness total \(n\) putative $\mathrm{ED}_n = 1$ means all distinct, and no proper subset of the symbols certifies that: whatever is left unread could duplicate something.
Ambainis-Belovs function partial \(O(n)\) At most $\mathrm{C} = O(n)$.
Ben-David-Kundu total search problems relation \(O(\log^6 n)\) The problem is total: every input has a valid output, so there is no "no" side and $\mathrm{C}^1 = \mathrm{C} = O(\log^6 n)$.
Yamakawa-Zhandry problem relation \(n\) The search problem is total -- every oracle admits a codeword all of whose symbols are preimages -- so there is no "no" side and $\mathrm{C}^1 = \mathrm{C} = n$.
Surjectivity total \(\Theta(n)\) putative A $1$-certificate names one preimage for each of the $R$ range values, which is $R\log_2 R = n/2$ bits at $R = N/2$, and that suffices.
$k$-distinctness total \(k\) putative Exhibit the $k$ positions carrying a repeated symbol. Counting a query as one symbol read, as throughout this entry and \(\mathrm{ED}_n\).
Triangle finding total \(3\) Name the three edges. This is the whole difficulty: with $N$ variables and $1$-certificates of size $K$, no positive-weight adversary can prove more than $\Omega(\sqrt{NK})$ [MSS07, §1], which for $N = m^2$, $K = 3$ is exactly the $\Omega(m)$ already on record. MSS07
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 See $\mathrm{C}^0$: the pair is $\{n, n-1\}$ and which side gets which depends only on the parity of $m$.
Minsky-Papert one-in-a-box total \(m\) A $1$-certificate names one $1$ in each of the $m$ boxes.
Sink of a tournament total \(m-1\) To certify a sink you must exhibit all $m-1$ of its in-edges, and that suffices.
Scorpion graphs total \(3m-6\) putative The $3m-6$ touch pairs of a triple $(s,t,b)$ are a certificate: they pin $N(s)=\{t\}$, $N(t)=\{s,b\}$ and $N(b) = V\setminus\{s\}$, and the feet may then do anything. So $3m-6 = \mathrm{s}^1 \le \mathrm{bs}^1 \le \mathrm{C}^1 \le 3m-6$ and all three coincide -- the scorpion is $1$-certificate-tight, verified by brute force for $m \le 9$.
Graph connectivity total \(m-1\) A spanning tree certifies connectivity.
Ben-David–Kothari championship function total \(O(n\log n)\) Lemma 2. BenDavidKothari26
Ambainis–Iraids–Kokainis unambiguous DNF total \(O(n)\) The satisfied term is a certificate. AIK26