Ambainis–Iraids–Kokainis unambiguous DNF
Log-free optimal separation $\mathrm{C}=\Theta(\mathrm{R}_{\mathrm{RP}}^2)$.
total arity: $n^2$ bits (even $n$)
Description
Partition $n^2$ bits into $n$ blocks $x_i$. Fix lists $P_j\in[n]^{8n}$ satisfying Lemma 3.1. For a half-sized set $S$, put $m_j(S)=\min\{a:P_j(a)\in S\}$ and $A_{ij}(S)=\{P_i(a):1\le a\le m_j(S)\}$. Term $T_{i,S}$ fixes block $i$ to the characteristic vector of $S$ and requires $x_j(p)=0$ for $j\ne i$ and $p\in A_{ij}(S)$. Accept iff a term is satisfied. The lists guarantee term width at most $9n$; terms are pairwise incompatible.
Formal definition
Fix even $n$, $k=n/2$, and lists $P_j\in[n]^{8n}$ satisfying Lemma 3.1 of [AIK26]. Put $m_j(S)=\min\{a:P_j(a)\in S\}$ and $A_{ij}(S)=\{P_i(a):1\le a\le m_j(S)\}$. $$T_{i,S}(x)=\left(\bigwedge_{p\in S}x_i(p)\right) \left(\bigwedge_{p\notin S}\neg x_i(p)\right) \left(\bigwedge_{j\ne i}\bigwedge_{p\in A_{ij}(S)}\neg x_j(p)\right), \qquad f_n(x)=\bigvee_{i\in[n],\,|S|=k}T_{i,S}(x).$$
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{C}(f)\) Certificate complexity | \(\Theta(n^2)\) | Theorem 2.2. AIK26 |
| \(\mathrm{C}^0(f)\) 0-certificate complexity | \(\Theta(n^2)\) | Lemma 3.4 and the input-size ceiling. AIK26 |
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(n)\) | Theorem 2.2 and the universal C = O(R²) bound. AIK26 |
| \(\mathrm{R}_{\mathrm{RP}}(f)\) One-sided randomized queries with certain rejection | \(\Theta(n)\) | Theorem 2.2; accepts only after a term is verified. AIK26 |
| \(\chi(f)\) Conflict complexity | \(\Theta(n)\) putative | Derived: AIK26 gives C=Θ(n²), R=Θ(n). The chain χ≤χ̄=O(LR)=O(R) gives χ=O(n); C≤bs² and χ≥(bs+1)/2 give χ=Ω(n). Thus C=Θ(χ²), refuting χ=Ω(C). AIK26 Nisan91 Li18 BBGM22 |
| \(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity | \(O(n)\) | Every 1-input satisfies exactly one term of width ≤9n. AIK26 |
| \(\mathrm{C}^1(f)\) 1-certificate complexity | \(O(n)\) | The satisfied term is a certificate. AIK26 |
| \(\deg(f)\) Exact degree | \(O(n)\) | A disjoint DNF equals the sum of its term indicators, each of degree ≤9n. AIK26 |
Separations its values prove — computed, not recorded
Read straight off the table above by comparing two values: no relation record states these, and where one does and says more, the record wins and the pair is not listed here. 5 in total.
-
\(\mathrm{C}(f_n) = \Omega\big(\mathrm{UC}_{\min}(f_n)^{2}\big)\)from \(\mathrm{C}(f) = \Theta(n^2)\) against \(\mathrm{UC}_{\min}(f) = O(n)\)
-
\(\mathrm{C}^0(f_n) = \Omega\big(\chi(f_n)^{2}\big)\)from \(\mathrm{C}^0(f) = \Theta(n^2)\) against \(\chi(f) = \Theta(n)\)
-
\(\mathrm{C}^0(f_n) = \Omega\big(\mathrm{UC}_{\min}(f_n)^{2}\big)\)from \(\mathrm{C}^0(f) = \Theta(n^2)\) against \(\mathrm{UC}_{\min}(f) = O(n)\)
-
\(\mathrm{C}^0(f_n) = \Omega\big(\deg(f_n)^{2}\big)\)from \(\mathrm{C}^0(f) = \Theta(n^2)\) against \(\deg(f) = O(n)\)
-
\(\mathrm{C}^0(f_n) = \Omega\big(\mathrm{R}_{\mathrm{RP}}(f_n)^{2}\big)\)from \(\mathrm{C}^0(f) = \Theta(n^2)\) against \(\mathrm{R}_{\mathrm{RP}}(f) = \Theta(n)\)
Cited as a witness by
-
\(\mathrm{C}(f_n)=\Theta(\chi(f_n)^2)\)
-
\(\mathrm{C}(f_n)=\Omega(\mathrm{R}(f_n)^2)\)
-
\(\mathrm{C}(f_n)=\Theta(\mathrm{R}_{\mathrm{RP}}(f_n)^2)\)