Minimum unambiguous certificate complexity
The cheaper of the two one-sided unambiguous certificate complexities.
Definition
$\mathrm{UC}_{\min}(f) = \min\{\mathrm{UC}^0(f),\ \mathrm{UC}^1(f)\}$ [BHT17, Sec. 2.5]: an unambiguous cover is demanded on only one side of the function, whichever side is cheaper. It is not a min over inputs -- $\mathrm{UC}_{\min}$ is still worst-case within the side it picks. It is the quantity in the $\mathrm{C}(f)=\Omega(\mathrm{UC}_{\min}(f)^{1.22})$ separation of [BHT17], which in turn drives the best known $\lambda$-vs-$\mathrm{C}$ separation.
Basic facts
- $\mathrm{D}(f) \le \mathrm{UC}_{\min}(f)^2$ and $\mathrm{C}(f) \le \mathrm{UC}_{\min}(f)^2$ [BHT17, Sec. 2.7.2]; the communication-complexity analogue is due to Yannakakis and the query-side proof to Goos.
- $\mathrm{fbs}(f) \le 2\,\mathrm{UC}_{\min}(f) - 1$ [BHT17, Thm 9], and the factor $2$ cannot be removed. This is exactly why the unambiguous-certificate route cannot produce a super-quadratic $\mathrm{bs}$-vs-$\mathrm{s}$ separation.
- $\mathrm{UC}_{\min}(f) \le \mathrm{UC}(f)$, but $\mathrm{UC}_{\min}$ is not above $\mathrm{C}$ -- only above $\mathrm{fbs}$.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{UC}_{\min}(f)\). “\(\mathrm{UC}_{\min}(f)\) in terms of it” is the pair with \(\mathrm{UC}_{\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 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\) putative | Corrected. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is the one-sided version, not a minimum over inputs. $\mathrm{UC}^0 = n$ because $0^n$ is the only $0$-input and its certificate must fix every bit. $\mathrm{UC}^1 = n$ too: an unambiguous $1$-cover partitions the $2^n-1$ ones-inputs into subcubes of sizes $2^{n-c_i}$, and an odd total forces some $c_i = n$. Consistent with the two general bounds $\mathrm{D} \le \mathrm{UC}_{\min}^2$ and $\mathrm{fbs} \le 2\,\mathrm{UC}_{\min}-1$ [BHT17], both of which the old value $1$ violated. BHT17 |
| AND total | \(n\) putative | Corrected, mirroring \(\mathrm{OR}_n\): $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is one-sided, not a minimum over inputs. $\mathrm{UC}^1 = n$ since $1^n$ is the only $1$-input, and $\mathrm{UC}^0 = n$ since an unambiguous $0$-cover partitions an odd number ($2^n-1$) of inputs into subcubes. The old value $1$ violated both $\mathrm{D} \le \mathrm{UC}_{\min}^2$ and $\mathrm{fbs} \le 2\,\mathrm{UC}_{\min}-1$ [BHT17]. BHT17 |
| PARITY total | \(n\) | Every certificate of every input is the whole assignment. |
| MAJORITY total | \(\Theta(n)\) | Sandwiched: $\mathrm{C}_{\min}(f) \le \mathrm{UC}_{\min}(f) \le \mathrm{UC}(f)$, with $\mathrm{C}_{\min}(f) = (n+1)/2$ and $\mathrm{UC}(f) = \Theta(n)$ here. |
| Threshold total | \(\Theta(n)\) putative | Immediately from $\mathrm{fbs}(f) \le 2\,\mathrm{UC}_{\min}(f)-1$ [BHT17] with $\mathrm{fbs} = \max\{k,\,n-k+1\}$, together with $\mathrm{UC}_{\min} \le \mathrm{UC} = \Theta(n)$. A self-contained route gives the same bound with better constants. Unambiguous covers restrict: intersecting each subcube of a cover with a subcube $\rho$ leaves an unambiguous cover of $f|_\rho$ of no larger width, so $\mathrm{UC}^b(f|_\rho) \le \mathrm{UC}^b(f)$. Fixing $k-1$ ones turns $\mathrm{THR}^n_k$ into $\mathrm{OR}_{n-k+1}$ and fixing $n-k$ zeros turns it into $\mathrm{AND}_k$; for both of these each side has an odd number of inputs ($2^m-1$, or the single point), so some subcube of any unambiguous cover has full codimension. Hence $\mathrm{UC}^0, \mathrm{UC}^1 \ge \max\{k,\,n-k+1\}$ and $\mathrm{UC}_{\min} = \Theta(n)$ -- the threshold family cannot witness anything for the [BHT17] $\mathrm{C}$-vs-$\mathrm{UC}_{\min}$ question. BHT17 |
| Symmetric functions (general) total | \(\Theta(n)\) | Squeezed: $\mathrm{fbs}(f) \le 2\,\mathrm{UC}_{\min}(f) - 1$ [BHT17] forces $\mathrm{UC}_{\min} = \Omega(n)$ since $\mathrm{fbs} = \Theta(n)$ here, and $\mathrm{UC}_{\min} \le \mathrm{UC} = \Theta(n)$. So symmetric functions are useless for the $\mathrm{C}$-vs-$\mathrm{UC}_{\min}$ separation of [BHT17]. BHT17 |
| EXACT-HALF total | \(\Theta(n)\) putative | Lower: $\mathrm{fbs} \le 2\,\mathrm{UC}_{\min}-1$ [BHT17] with $\mathrm{fbs} = n$ gives $\mathrm{UC}_{\min} \ge (n+1)/2$. Upper: $\mathrm{UC}_{\min} \le \mathrm{UC}^1 = n$, the $1$-inputs being isolated points, which the partition into singletons covers unambiguously. The exact constant is open here; note that no unambiguous $0$-cover can use only minimum $0$-certificates, since two all-ones certificates of size $n/2+1$ must overlap in a coordinate and their subcubes then share the input $1_{S \cup T}$. BHT17 |
| ODD-MAX-BIT total | \(\Theta(n)\) | Squeezed: $\mathrm{fbs}(f) \le 2\,\mathrm{UC}_{\min}(f)-1$ [BHT17] forces $\mathrm{UC}_{\min} \ge \tfrac12(\lfloor n/2\rfloor+2) = \Omega(n)$, and $\mathrm{UC}_{\min} \le \mathrm{UC} = \Theta(n)$. Note the contrast with $\mathrm{C}_{\min} = 1$: the one-sided unambiguous measure is not a minimum over inputs and does not collapse. BHT17 |
| ADDRESS / multiplexer total | \(k+1\) | Between $\mathrm{C}_{\min} = k+1$ and $\mathrm{UC} = k+1$. |
| Binary tree navigation total | \(k\) | Sandwiched: $\mathrm{C}_{\min}(f) \le \mathrm{UC}_{\min}(f) \le \mathrm{UC}(f)$, with both ends $k$ here -- navigation is completely certificate-uniform, so none of the four certificate variants can separate. |
| TRIBES total | \(n\) putative | Both sides are $n$ by the parity argument on the \(\mathrm{UC}(f)\) line, so the one-sided minimum does not help. TRIBES is therefore useless as a witness for the [BHT17] $\mathrm{C}$-vs-$\mathrm{UC}_{\min}$ question, despite its very lopsided certificate complexities. BHT17 |
| AND-OR tree (depth 2) total | \(N = n^2\) putative | An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min} \le \mathrm{UC}$. Here $\deg = \mathrm{UC} = n^2$, so even the cheaper side of the unambiguous cover costs the full $N$ -- against $\mathrm{C}_{\min} = n$. |
| NAND tree (balanced AND-OR formula) total | \(N\) putative | An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min}$. On a read-once formula $\deg = \mathrm{D} = N$, so even the cheaper side is full -- against $\mathrm{C}_{\min} = \Theta(\sqrt N)$, a quadratic $\mathrm{UC}_{\min}$-vs-$\mathrm{C}_{\min}$ gap. |
| Recursive MAJORITY-of-3 total | \(N = 3^d\) putative | An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min} \le \mathrm{UC}$. Here $\deg = \mathrm{UC} = N$, so both unambiguous sides cost the full $N$ against $\mathrm{C} = \mathrm{C}_{\min} = N^{0.63}$. |
| Kushilevitz's function (iterated) total | \(\Omega(N^{0.6131}),\ O(N)\) putative | Not pinned. Lower: an unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\mathrm{UC}_{\min} \ge \deg = 3^k$. Upper: $\mathrm{UC}_{\min} \le \mathrm{UC} = N$. Unlike the read-once functions in this file, $\deg \ne \mathrm{D}$ here, so the squeeze leaves a genuine $N^{0.39}$ window. |
| Rubinstein's function total | \(N\) putative | An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min} \le \mathrm{UC}$. Here $\deg = \mathrm{UC} = N$, so both sides are pinned -- against $\mathrm{C}_{\min} = \sqrt N$. |
| Ambainis-Sun function total | \(\Theta(N)\) putative | An unambiguous $b$-certificate family of width $w$ writes $f$ (for $b=1$) or $1-f$ (for $b=0$) as a sum of indicators of disjoint subcubes of codimension $\le w$, so nothing cancels and $\deg(f) \le \min\{\mathrm{UC}^0,\mathrm{UC}^1\} = \mathrm{UC}_{\min}$. Here $\deg = (3k+2)^2 = \Theta(N)$ and $\mathrm{UC} = \Theta(N)$, so both sides are pinned. |
| AND composed with NOT-EXACT-HALF total | \(\Theta(n^2)\) putative | An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as a sum of indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg \le \mathrm{UC}^0$ and $\deg \le \mathrm{UC}^1$, i.e. $\deg \le \mathrm{UC}_{\min} \le \mathrm{UC}$. Here $\deg = \mathrm{UC} = \Theta(n^2)$, so both sides are pinned -- against $\mathrm{C}_{\min} = n$. |
| Meiburg's tournament-subcube function total | \(\ge 118.3^{\,d}\) putative | An unambiguous $b$-certificate family of width $w$ writes $f$ (or $1-f$) as the sum of the indicators of disjoint subcubes of codimension $\le w$, with no cancellation, so $\deg(f) \le \mathrm{UC}^0$ and $\deg(f) \le \mathrm{UC}^1$, hence $\deg \le \mathrm{UC}_{\min}$. With $\deg \ge \sqrt{\mathrm{bs}} \ge 118.3^{\,d}$ from the \(\deg(f)\) entry this is the bound; the alternative route $\mathrm{D} \le \mathrm{UC}_{\min}^2$ gives the same $\sqrt{14011^{\,d}}$. |
| Pointer functions total | \(\widetilde\Omega(\sqrt n)\) | Squeeze: $\mathrm{D}=O(\mathrm{UC}_{\min}^2)$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n)$, which holds on every variant. BHT17 |
| Cheat-sheet functions total | \(\widetilde\Theta(\sqrt n)\) | Upgraded to a two-sided bound: the upper bound below, plus $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\widetilde\Theta(n)$. The same uniqueness makes the $1$-certificates of $\mathrm{BKK}_{\mathrm{CS}}$ unambiguous, giving $\mathrm{Q}=\widetilde\Omega(\mathrm{UC}_{\min}^2)$ [BHT17, Cor. 2, attributed to AKK16]. This is the input to the \(f_{\mathrm{BHT}}\) amplification. BHT17 |
| Low-sensitivity function from unambiguous certificates total | \(\widetilde\Omega(n^{3/2})\) | Squeeze: $\mathrm{D}=O(\mathrm{UC}_{\min}^2)$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n^3)$. Note this is the output of the amplification, not the $\mathrm{UC}_{\min}$ of the base function that sets the scale variable. BHT17 |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde\Theta(n)\) | Upper: $\mathrm{UC}_{\min}\le\mathrm{UC}_1\le 3\,\mathrm{C}(\mathrm{Eah}_n)\log^2 N=\widetilde O(n)$ [BBGJK21, Claim 17] -- read one certificate per copy plus the whole indexed cell. Lower: $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n^2)$. BBGJK21 |
| Gilmer-Saks-Srinivasan functions total | \(\Omega(n)\) | Squeeze: $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\Theta(n^2)$ (equally, $\mathrm{UC}_{\min}\ge\min\{\mathrm{C}^0,\mathrm{C}^1\}=n$). Unlike \(f_{\mathrm{GPW}}\) there is no matching upper bound: the $1$-certificates here are not unambiguous, since several copies can be $1$ at once. BHT17 |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde\Theta(\sqrt n)\) | Upper $\mathrm{UC}_{\min}\le\mathrm{UC}_1=\widetilde O(\sqrt n)$; lower from $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n)$. The quadratic $\mathrm{D}$-vs-$\mathrm{UC}_{\min}$ gap is therefore optimal up to logarithms. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde\Theta(n^{1/3})\) | Upper $\mathrm{UC}_{\min}\le\mathrm{UC}_1=\widetilde O(n^{1/3})$; lower from $\mathrm{D}\le\mathrm{UC}_{\min}^2$ [BHT17] against $\mathrm{D}=\widetilde\Omega(n^{2/3})$. |
| Ambainis' exact-quantum function total | \(\Theta(3^d)\) | Squeeze: an unambiguous certificate family is in particular a certificate family, so $\mathrm{UC}_{\min}\ge\min\{\mathrm{C}^0,\mathrm{C}^1\}=(3^d+1)/2$; and $\mathrm{UC}_{\min}\le\mathrm{UC}=3^d$. Both sides of this function are expensive to certify even ambiguously, so the [BHT17] route to a low-sensitivity function gets no traction here. |
| FORRELATION partial | \(\Theta(n)\) | Squeezed between $\mathrm{C}_{\min} = \Theta(n)$ and $\mathrm{UC} = \Theta(n)$. Note this is the one-sided minimum $\min\{\mathrm{UC}^0,\mathrm{UC}^1\}$, and both sides are already $\Theta(n)$ here. |
| k-FORRELATION partial | \(O(kn)\) | At most $\mathrm{UC}$. |
| Simon's problem partial | \(O(2^{n/2})\) | Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = \Theta(2^{n/2})$, and nothing sharper is available. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs: the cheap two-query collision certificates on the "periodic" side are massively ambiguous, since a periodic $g$ contains $2^{n-1}$ of them, and disambiguating them by "first collision in lex order" costs the full $\Theta(2^{n/2})$ again. |
| Deutsch-Jozsa partial | \(O(N)\) | Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = N/2 + 1$. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs, so the width-$2$ certificates on the balanced side do not give $O(1)$: a balanced input has $N^2/4$ disagreeing pairs, and an unambiguous family must still name one of them, which is the same obstruction that forces $\mathrm{UC} = \Omega(N)$. |
| Bernstein-Vazirani partial | \(n\) putative | Squeezed between $\mathrm{C}_{\min} = n$ and $\mathrm{UC} = n$. |
| Unique search partial | \(1\) putative | The $1$-certificates of that cover have width $1$, so $\mathrm{UC}^1 = 1$. With $\mathrm{D} = n$ this shows the total-function bound $\mathrm{D} \le \mathrm{UC}_{\min}^2$ [BHT17] is total-only. |
| Gap-Majority partial | \(\Theta(n)\) putative | Squeezed between $\mathrm{C}_{\min}$ and $\mathrm{UC}$, both $\Theta(n)$. |
| Gap-Majority at constant gap partial | \(\Theta(n)\) putative | Between $\mathrm{C}_{\min}$ and $\mathrm{UC}$. |
| Approximate index partial | \(O(\sqrt{k\log k})\) | Between $\mathrm{C}_{\min} = \Theta(1)$ and $\mathrm{UC}$. |
| Collision problem partial | \(O(n)\) | Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = n/2 + 1$. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs: a two-to-one $g$ has $n/2$ collision pairs, so the width-$2$ collision certificates overlap heavily and no unambiguous family of constant width covers that side. |
| Element distinctness total | \(O(n)\) | Squeezed between $\mathrm{C}_{\min} = 2$ and $\mathrm{UC} = n$. $\mathrm{UC}_{\min} = \min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ is worst-case within the cheaper side, not a minimum over inputs, so the width-$2$ collision certificates (which live on the $0$-side under the convention $\mathrm{ED}_n = 1$ on all-distinct inputs) do not give $O(1)$: an input with many repeats has many such pairs and the family must disambiguate them. |
| Ambainis-Belovs function partial | \(O(n)\) | At most $\mathrm{UC} = O(n)$. |
| Surjectivity total | \(\Omega(n/\log n),\ O(n)\) | $\mathrm{UC}^b\ge\mathrm{C}^b$ on each side, so $\mathrm{UC}_{\min}\ge\min\{\mathrm{C}^0,\mathrm{C}^1\}=\Theta(n/\log n)$, and $\mathrm{UC}_{\min}\le\mathrm{UC}=\Theta(n)$. Which side is cheaper is exactly the open part: the $0$-certificates are the short ones. BHT17 |
| Triangle finding total | \(\Theta(m^2)\)· putative | $\mathrm{UC}^0\ge\mathrm{C}^0=\binom m2$, so the question is the $1$-side. For the input consisting of a single triangle $T$, any certificate must fix a triangle to $1$ and can only fix edges of $T$, so its $1$-part is exactly $T$. For two distinct triangles $T$ and $U$ the graph $T\cup U$ then lies in both certificates unless one of them fixes an edge of the other to $0$; orienting each such pair, some triangle beats at least half the others, and since each edge lies in $m-2$ triangles its $0$-set has size $\Omega(m^2)$. Hence $\mathrm{UC}^1=\Theta(m^2)$ too, and the ceiling is $\mathrm{UC}=\binom m2$. BHT17 |
| Ordered search partial | \(2\) | $\mathrm{UC}_{\min}=\min\{\mathrm{UC}^0,\mathrm{UC}^1\}$ [BHT17], and both sides are $2$ by the family of the \(\mathrm{UC}(f)\) entry; the floor is $\mathrm{C}_{\min}$ on the relevant side. BHT17 |
| Inner product mod 2 total | \(n/2\) putative | That same partition gives the input $x = 0^m$ a certificate of size $m$, and no certificate anywhere is smaller than $\mathrm{C}_{\min} = m$. |
| Minsky-Papert one-in-a-box total | \(N = m^3\) putative | The parity argument recorded for \(\mathrm{UC}(f)\) works on both sides, so the one-sided relaxation buys nothing. $|f^{-1}(1)| = (2^{m^2}-1)^m$ is odd, and $|f^{-1}(0)| = 2^{N} - (2^{m^2}-1)^m$ is even minus odd, hence also odd. An unambiguous $b$-certificate family partitions $f^{-1}(b)$ into subcubes of sizes $2^{N-w_i}$; an odd total forces some $w_i = N$. So $\mathrm{UC}^0 = \mathrm{UC}^1 = N$ and $\mathrm{UC}_{\min} = N = m^3$, against $\mathrm{C} = m^2$. This is an extreme point of $\mathrm{C} \ge \mathrm{UC}_{\min}^{1.22}$-type separations in the opposite direction: here $\mathrm{UC}_{\min}$ is as far above $\mathrm{C}$ as $\mathrm{D} \le \mathrm{UC}_{\min}^2$ allows it to be useful at all. |
| Sink of a tournament total | \(\Theta(m) = \Theta(\sqrt N)\) | Sandwiched: $\mathrm{C}_{\min} \le \mathrm{UC}_{\min} \le \mathrm{UC}$, with $\mathrm{C}_{\min} = m-1$ and $\mathrm{UC} = \Theta(m)$ here. |
| Scorpion graphs total | \(\Theta(m)\) | Sandwiched: $\mathrm{C}_{\min} \le \mathrm{UC}_{\min} \le \mathrm{UC}$, with $\mathrm{C}_{\min} = m-1$ and $\mathrm{UC} = \Theta(m)$ here. |
| Graph connectivity total | \(\Theta(m^2) = \Theta(N)\) putative | The one-sided relaxation buys nothing, but for a softer reason than on \(\mathrm{MP}_m\): the $0$-side is genuinely cheap to cover unambiguously and it is still $\Theta(N)$. Cover: for each connected vertex set $S \ni v_1$ with $S \ne V$, take the certificate that specifies every edge inside $S$ together with all $|S|(m-|S|)$ cross edges absent. Each disconnected graph matches exactly one of these -- $S$ is forced to be the component of $v_1$ -- so $\mathrm{UC}^0 \le N$, and $\mathrm{UC}^0 \ge \mathrm{C}^0 = \Theta(m^2)$. The lower bound on the min is $\mathrm{fbs} \le 2\,\mathrm{UC}_{\min} - 1$ (\(\mathrm{fbs}(f)\) vs \(\mathrm{UC}_{\min}(f)\)) with $\mathrm{fbs} = \Theta(m^2)$. |
| Ambainis–Iraids–Kokainis unambiguous DNF total | \(O(n)\) | Every 1-input satisfies exactly one term of width ≤9n. AIK26 |
| Pabbaraju’s optimal unambiguous DNF total | \(O(n)\) | Theorem 1 gives UC¹=O(n). Pabbaraju26 |