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.
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\) | |
| 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 |