Pabbaraju’s optimal unambiguous DNF
$\mathrm{C}^0=\Omega(n^2)$ and $\mathrm{UC}^1=O(n)$, without logarithmic losses.
total arity: $n^2$ bits
Description
The unambiguous DNF of Theorem 1 on $n$ blocks of $n$ bits. Terms select a block and a half-sized positive set, and signed set-pair systems specify the cross-block negative literals (Section 3). Every term has width $O(n)$, distinct terms are incompatible, and the all-zero input needs $\Omega(n^2)$ bits to certify rejection.
Formal definition
Fix disjoint blocks $B_1,\ldots,B_n$ of size $n$ and $k=\lfloor n/2\rfloor$. For every unordered pair $\{i,j\}$ choose bijections $\pi_i^{ij}:B_i\to[n]$, $\pi_j^{ij}:B_j\to[n]$ with $\sum_{j\ne i}\min_{u\in S}\pi_i^{ij}(u)=O(n)$ uniformly over $i$ and $k$-subsets $S\subseteq B_i$; [Pabbaraju26, Section 3] proves such choices exist. Put $a_{ij}(S)=\min_{u\in S}\pi_i^{ij}(u)$ and $A_{ij}(S)=\{v\in B_j:\pi_j^{ij}(v)\le a_{ij}(S)\}$. $$f_n(x)=\bigvee_{i,\,S\subseteq B_i,\,|S|=k} \left(\bigwedge_{u\in S}x_u\right) \left(\bigwedge_{v\in(B_i\setminus S)\cup\bigcup_{j\ne i}A_{ij}(S)}\neg x_v\right).$$
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(\Omega(n^2)\) | Theorem 1. Pabbaraju26 |
| \(\mathrm{C}(f)\) Certificate complexity | \(\Theta(n^2)\) | C≥C₀ and C≤n². Pabbaraju26 |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(O(n)\) | Theorem 1 gives UC¹=O(n). Pabbaraju26 |
| \(\deg(f)\) Exact degree | \(O(n)\) | Corollary 1.2: exact representation by the sum of disjoint term indicators. Pabbaraju26 |
Cited as a witness by
-
\(\mathrm{C}(f_n)=\Omega(\deg(f_n)^2)\)