Nondeterministic degree
Least degree of a polynomial that is nonzero exactly on the 1-inputs.
Definition
The least degree of $p$ with $p(x)\ne 0 \iff f(x)=1$ (on the domain). de Wolf: $\mathrm{NQ}(f)=\lceil\mathrm{ndeg}(f)/2\rceil$, and $\mathrm{rdeg}(f)=\max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\}$.
Basic facts
- $\mathrm{ndeg}(f)\le\mathrm{C}^1(f)$.
Relations to other measures
A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{ndeg}(f)\). “\(\mathrm{ndeg}(f)\) in terms of it” is the pair with \(\mathrm{ndeg}(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\) | $p(x)=\sum_i x_i$ vanishes exactly on $\mathrm{OR}^{-1}(0)$. |
| AND total | \(n\) | |
| PARITY total | \(n\) | |
| MAJORITY total | \((n+1)/2\) putative | Exactly. Upper: $\prod_{j=0}^{(n-1)/2}(|x|-j)$ vanishes exactly on the $0$-inputs. Lower: $\mathrm{MAJ}_n = \mathrm{THR}^n_{(n+1)/2}$, and restricting $(n-1)/2$ variables to $0$ leaves $\wedge_{(n+1)/2}$, whose nondeterministic degree is $(n+1)/2$ (the \(\mathrm{AND}_n\) line); $\mathrm{ndeg}$ cannot increase under restriction. This is the \(\mathrm{THR}^n_k\) value $\mathrm{ndeg} = k$ at $k = (n+1)/2$. |
| Threshold total | \(k\) putative | Upper: $\prod_{j=0}^{k-1}(|x|-j)$ is nonzero exactly on the $1$-inputs and has degree $k$. Lower: let $S$ be a minimal set in the Fourier-style monomial support of a witnessing multilinear $p$; then $p(1_S) = \sum_{T \subseteq S} c_T = c_S \ne 0$, so $1_S$ is a $1$-input and $|S| \ge k$. Dually $\mathrm{ndeg}(\bar f) = n-k+1$. |
| Symmetric functions (general) total | \(\Theta(\#\{j \,:\, f_j = 0\})\) putative | Upper: $\prod_{j : f_j = 0}(|x|-j)$ is nonzero exactly on the $1$-inputs. Lower: if $p$ witnesses $\mathrm{ndeg}$ then $p^2$ is non-negative, vanishes exactly on the $0$-inputs, and its symmetrisation $j \mapsto \mathbb{E}_{|x|=j}[p(x)^2]$ is a univariate polynomial of degree at most $2\deg p$ that is strictly positive on the $1$-slices and zero on the $0$-slices, hence has at least $\#\{j : f_j = 0\}$ roots. So $\mathrm{ndeg}$ is pinned to within a factor $2$. Like the \(\mathrm{sdeg}(f)\) line this is a display-only value: it is a function of the slice pattern, not of $n$ and $\Gamma(f)$. Recovers $\mathrm{ndeg}(\mathrm{OR}) = 1$, $\mathrm{ndeg}(\mathrm{AND}) = n$ and $\mathrm{ndeg}(\mathrm{THR}^n_k) = k$. |
| EXACT-HALF total | \(n/2\) putative | Exactly $n/2$, for $\mathrm{EH}_n$ itself. Upper bound: for a perfect matching $M$ of $[n]$ put $q_M(x)=\prod_{(i,j)\in M}(x_i-x_j)$, of degree $n/2$; it is nonzero iff every pair of $M$ is split, which forces $|x| = n/2$, and every middle input is split by some matching. So a generic combination $\sum_M a_M q_M$ is nonzero exactly on the middle slice. Lower bound: if $p$ is nonzero exactly on $\mathrm{EH}^{-1}(1)$ then $p^2$ is nonnegative with the same zero set, so its symmetrisation $P(k)=\mathbb{E}_{|x|=k}[p(x)^2]$ is a univariate polynomial of degree $\le 2\deg p$ vanishing at all $n$ points $k \ne n/2$ of $\{0,\dots,n\}$; hence $\deg p \ge n/2$. Contrast $\mathrm{ndeg}(\overline{\mathrm{EH}}_n) = 1$, witnessed by $\sum_i x_i - n/2$: this factor-$n/2$ asymmetry between a function and its negation is what \(\mathrm{EH}_n\) is for, and it is what makes $\mathrm{rdeg} = \max\{\mathrm{ndeg}(f),\mathrm{ndeg}(\bar f)\} = n/2$ here. IJKKKSWW23 |
| ODD-MAX-BIT total | \(\lfloor n/2 \rfloor + 1\) putative | Exactly. Upper: $\mathrm{ndeg} \le \mathrm{C}^1 = \lfloor n/2\rfloor + 1$ (the \(\mathrm{C}^1(f)\) line). Lower: set every odd position $\ge 3$ to $0$ and leave $x_1$ together with the $\lfloor n/2\rfloor$ even positions free; the restriction is $1$ iff $x_1 = 1$ and all even positions are $0$, an $\mathrm{AND}$ on $\lfloor n/2\rfloor+1$ variables with some of them negated. Nondeterministic degree cannot increase under restriction or under negating variables, and $\mathrm{ndeg}(\wedge_m) = m$ (the \(\mathrm{AND}_n\) line). Exhaustive computation of the minimal witnessing degree for $n \le 9$ agrees. deWolf03 |
| ADDRESS / multiplexer total | \(\Theta(k)\) | Upper: $\mathrm{ndeg} \le \mathrm{C}^{1} = k+1$, and in fact $\sum_a \mathbb{1}[\mathrm{addr}=a]\,y_a$ is the function, of degree $k+1$. Lower: restrict the data table to $e_{a_0}$; the restriction is $\mathbb{1}[\mathrm{addr}=a_0]$, and a polynomial that is nonzero at exactly one point of $\{0,1\}^k$ is a scalar multiple of that point indicator, of degree $k$. So $\mathrm{ndeg} \in \{k, k+1\}$. |
| Binary tree navigation total | \(\Theta(k)\) putative | Upper: $f$ itself is $0/1$-valued, so its exact multilinear polynomial is nonzero precisely on the $1$-inputs, giving $\mathrm{ndeg} \le \deg = k$. Lower: the property "nonzero exactly on the $1$-inputs" survives the substitution of the \(\widetilde{\deg}_{\varepsilon}(f)\) line, so $\mathrm{ndeg}(\mathrm{Nav}_k) \ge \mathrm{ndeg}(\mathrm{PARITY}_{k-1}) = k-1$. |
| TRIBES total | \(\Theta(\log n)\) putative | Exactly $w$. Upper: $p(x) = \sum_j \prod_{i \in T_j} x_i$ is a sum of nonnegative terms that vanishes precisely when no tribe is all-ones, and has degree $w$. Lower: kill all but one tribe by planting a $0$ in each of the others; the restriction is $\mathrm{AND}_w$, whose nondeterministic degree is $w$ because a polynomial vanishing on all but one point of the cube needs full degree. Contrast $\deg = n$: the \(\mathrm{rdeg}(f)\) gap comes entirely from the other side. |
| AND-OR tree (depth 2) total | \(n = \sqrt N\) | Nondeterministic degree is multiplicative over the disjoint blocks of an AND: $\mathrm{ndeg}(\mathrm{AND}_n\circ g) = n\,\mathrm{ndeg}(g)$, and $\mathrm{ndeg}(\mathrm{OR}_n) = 1$ (the polynomial $\sum_i x_i$ is nonzero exactly on the $1$-inputs). This is the $\mathrm{ndeg}(f) = n$ half of the recorded \(\mathrm{rdeg}(f)\) value. IJKKKSWW23 |
| NAND tree (balanced AND-OR formula) total | \(2^{\lfloor d/2\rfloor} = \Theta(\sqrt N)\) putative | Write $f_d = \mathrm{OR}_2(\overline{f_{d-1}},\overline{f_{d-1}})$ and $\overline{f_d} = \mathrm{AND}_2(f_{d-1},f_{d-1})$, and set $a_d = \mathrm{ndeg}(f_d)$, $b_d = \mathrm{ndeg}(\overline{f_d})$. Nondeterministic degree is exactly multiplicative over the disjoint blocks of an $\mathrm{AND}$ [IJKKKSWW23], so $b_d = 2a_{d-1}$. For the $\mathrm{OR}$ level: restricting one block to a $0$-input of $\overline{f_{d-1}}$ gives $a_d \ge b_{d-1}$, while $a_d \le \mathrm{C}^1(f_d) = \mathrm{C}^0(f_{d-1}) = 2^{\lceil (d-1)/2\rceil} = 2^{\lfloor d/2\rfloor}$ (sum the indicators of the $1$-certificates -- all coefficients positive, so no cancellation). With $a_0 = b_0 = 1$ and $a_1 = 1$ (witness $1+x_1-2x_2$ for $\mathrm{NAND}_2$) the two ends meet and $a_d = 2^{\lfloor d/2\rfloor}$ exactly, matching the recorded $\mathrm{C}^1$. IJKKKSWW23 |
| Recursive MAJORITY-of-3 total | \(\Omega(1.732^{\,d}),\ O(2^d)\) | Upper: $\mathrm{ndeg} \le \mathrm{C}^1 = 2^d$ (sum the indicators of the $1$-certificates; all coefficients are positive, so nothing cancels), already a factor $(3/2)^d$ below $\deg = 3^d$. Lower: $\mathrm{MAJ}_3^{\circ d}$ is self-dual, so $\mathrm{ndeg}(\bar f) = \mathrm{ndeg}(f)$ and therefore $\mathrm{ndeg} = \mathrm{rdeg}$; recursive majority is a read-once $\mathsf{TC}^0$ formula, for which $\mathrm{rdeg} = \Omega(\sqrt{\deg}) = \Omega(3^{d/2}) = \Omega(1.732^{\,d})$ [IJKKKSWW23]. IJKKKSWW23 |
| Kushilevitz's function (iterated) total | \(\le 3^k = N^{0.6131}\) | $\mathrm{ndeg} \le \deg = 3^k$ (a polynomial computing $f$ exactly is in particular nonzero exactly on $f^{-1}(1)$). The other generic bound $\mathrm{ndeg} \le \mathrm{C}^1 = N$ is much weaker here, which is the whole point of this function: its degree is polynomially smaller than its certificate complexity. IJKKKSWW23 |
| Rubinstein's function total | \(\le n = \sqrt N\) | $\mathrm{ndeg} \le \mathrm{C}^1 = n$: sum the indicators of the $n$-bit $1$-certificates (one per block pattern), all with positive coefficients, so the sum is nonzero exactly on $f^{-1}(1)$. Note this is $\sqrt{\deg}$ -- an extreme example of nondeterministic degree collapsing below the exact degree $N$. IJKKKSWW23 |
| Ambainis-Sun function total | \(\le 3k+2\) | $\mathrm{ndeg} \le \mathrm{C}^1 = 3k+2$ (sum the $1$-certificate indicators, all with positive coefficients). Since $\deg = (3k+2)^2$, nondeterministic degree is at most $\sqrt{\deg}$ here -- the same quadratic collapse as in \(f_{\mathrm{Rub}}\). IJKKKSWW23 |
| AND composed with NOT-EXACT-HALF total | \(n = \sqrt N\) | The $\mathrm{ndeg}(f) = n$ half of the recorded \(\mathrm{rdeg}(f)\) value: $\mathrm{ndeg}(\overline{\mathrm{EH}}_n) = 1$, witnessed by $p(x) = \sum_i x_i - n/2$, and nondeterministic degree multiplies over the disjoint blocks of an AND, $\mathrm{ndeg}(\mathrm{AND}_n\circ g) = n\,\mathrm{ndeg}(g)$. IJKKKSWW23 |
| Meiburg's tournament-subcube function total | \(\le 7923.9^{\,d}\) putative | A polynomial computing $f$ exactly is nonzero exactly on $f^{-1}(1)$, so $\mathrm{ndeg} \le \deg \le 7923.9^{\,d}$. The competing bound $\mathrm{ndeg} \le \mathrm{C}^1$ of [IJKKKSWW23] gives $7149\cdot 14011^{\,d-1}$, which is worse for $d \ge 2$. IJKKKSWW23 |
| Pointer functions total | \(\widetilde O(\sqrt n)\) | Variant $f_{2m,m}$: $\mathrm{ndeg}\le\mathrm{C}^1=\widetilde\Theta(\sqrt n)$ -- sum the $1$-certificate indicator conjunctions, which are non-negative and cannot cancel. |
| Cheat-sheet functions total | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{ndeg}\le\min\{\mathrm{C}^1,\deg\}=\widetilde O(\sqrt n)$. Against $\mathrm{Q}=\widetilde\Theta(n)$ this is a quadratic gap. |
| Unambiguous-DNF / Alon-Saks-Seymour function total | \(\widetilde O(n)\) | Squeeze: $\mathrm{ndeg}\le\min\{\mathrm{C}^1,\deg\}=\widetilde O(n)$; here the two bounds happen to agree, both coming from $\mathrm{UC}_1$. |
| Gilmer-Saks-Srinivasan functions total | \(O(n)\) | Squeeze: $\mathrm{ndeg}\le\mathrm{C}^1=n$ -- sum the indicator conjunctions of the $1$-certificates, which are non-negative and cannot cancel. Against $\mathrm{C}=\Theta(n^2)$ this is a clean quadratic gap. |
| Goos-Pitassi-Watson partition-number function total | \(\widetilde O(\sqrt n)\) | Squeeze: $\mathrm{ndeg}\le\min\{\mathrm{C}^1,\deg\}=\widetilde O(\sqrt n)$; both bounds trace back to the same unambiguous $1$-certificates. |
| Goos-Jayram-Pitassi-Watson function total | \(\widetilde O(n^{1/3})\) | Squeeze: $\mathrm{ndeg}\le\min\{\mathrm{C}^1,\deg\}=\widetilde O(n^{1/3})$, both bounds coming from the unambiguous $1$-certificates. |
| Ambainis' exact-quantum function total | \(O(2^d)\) | Squeeze: $\mathrm{ndeg}\le\min\{\mathrm{C}^1,\deg\}=2^d$ (the certificate bound is the weaker one here, $(3^d+1)/2$). Already at $d=1$ the real form $x_1+x_2+x_3-(x_1x_2+x_1x_3+x_2x_3)$ is nonzero exactly on the $1$-inputs, so $\mathrm{ndeg}(\mathrm{NE})=2$. No floor is recorded: nondeterministic degree has no $\sqrt{\mathrm{bs}}$-type lower bound. |
| FORRELATION partial | \(O(n)\) | At most $\mathrm{C}^1 = \Theta(n)$: the sum over $1$-certificates of their indicator polynomials is a nondeterministic polynomial. |
| k-FORRELATION partial | \(O(kn)\) | At most $\mathrm{C}^1 \le \mathrm{C} = O(kn)$. |
| Simon's problem partial | \(\Theta(1)\) | At most $\mathrm{C}^1 = 2$, the colliding pair: put $p = \sum_{x<y} \mathbb{1}[g(x) = g(y)]$, a degree-$2$ polynomial in the indicator variables that is $0$ on injective inputs and positive on two-to-one ones. |
| Deutsch-Jozsa partial | \(1\) putative | Nondeterministic degree collapses where ordinary degree does not. Take $p = \sum_i c_i x_i$ with $\sum_i c_i = 0$ and the $c_i$ otherwise generic: then $p$ vanishes at $0^N$ and at $1^N$, while $\sum_{i \in \mathrm{supp}(y)} c_i \ne 0$ for every balanced $y$ because generic points of the hyperplane $\sum c_i = 0$ avoid the finitely many further hyperplanes. So $\mathrm{ndeg} = 1 < \deg = 2$. |
| Unique search partial | \(1\) | $\sum_i x_i$ is nonzero exactly on the $1$-inputs of the domain. |
| Two-or-none search partial | \(1\) | $\sum_i x_i$ is nonzero exactly on the $1$-inputs of the domain. |
| Marked bit partial | \(1\) | $\sum_b y_b$ is nonzero exactly on the $1$-inputs of the domain. And $\mathrm{ndeg} \ge 1$. |
| Dense marked bit partial | \(1\) | $\sum_b y_b$ is nonzero exactly on the $1$-inputs of the domain, and $\mathrm{ndeg} \ge 1$. |
| Gap-Majority partial | \(\Theta(n)\) putative | Same symmetrisation, applied to $p^2$: if $p$ is nonzero exactly on the $1$-inputs then $q(t) = \mathbb{E}_{|x|=t}[p(x)^2]$ is a non-negative univariate polynomial of degree $\le 2\,\mathrm{ndeg}$ vanishing at all $(1/2-\delta)n$ integers $t \le n/2-\delta n$ and nonzero above $n/2+\delta n$, so $\mathrm{ndeg} \ge (1/4-\delta/2)n$; and $\mathrm{ndeg} \le \mathrm{C}^1 = \Theta(n)$. |
| Gap-Majority at constant gap partial | \(\Theta(n)\) putative | Same symmetrisation applied to $p^2$; and $\mathrm{ndeg} \le \mathrm{C}^1$. |
| Parity-labelled FIND-1 partial | \(1\) putative | $\sum_{i \text{ odd}} x_i$ is nonzero on the domain exactly at the $1$-inputs. |
| Approximate index partial | \(\Theta(1)\) | $\mathrm{ndeg} \le \mathrm{C}^1 = \Theta(1)$ -- take the sum over $1$-certificates of the product of their literal indicators, which is nonzero exactly on the $1$-inputs of the domain (a $0$-input containing a $1$-certificate would be a domain point of both values). And $\mathrm{ndeg} \ge 1$. |
| Collision problem partial | \(2\) putative | Exactly $2$: the polynomial $\sum_{i<j}\sum_v x_{i,v}x_{j,v}$ counts colliding pairs, so it is nonzero precisely on the two-to-one side, and no linear form can do that. Equivalently $\mathrm{ndeg} \le \mathrm{C}^1 = 2$. |
| Element distinctness total | \(\Theta(n)\) putative | Upper: $\mathrm{ndeg} \le \mathrm{C}^1 = n$. Lower: restrict to $x_i \in \{0,i\}$ as in the \(\deg(f)\) entry, so that $\mathrm{ED}_n$ becomes "at most one $z_i = 1$". A multilinear $p$ that is nonzero exactly on the $n+1$ points of weight $\le 1$ has Moebius coefficients $c_S = (-1)^{|S|}(a_0 - \sum_{i \in S} a_i)$ for $|S| \ge 1$, where $a_0 = p(0)$ and $a_i = p(e_i)$ are all nonzero. Killing every coefficient of degree $n$ forces $a_0 = \sum_i a_i$, and killing every coefficient of degree $n-1$ forces $a_0 = \sum_{i \ne j} a_i$ for each $j$; together these give $a_j = 0$, a contradiction. Hence $\mathrm{ndeg} \ge n-1$. |
| Ambainis-Belovs function partial | \(O(1)\) | The exact representation $T(K(x)/n)$ is nonzero exactly on the $1$-inputs of the domain, so $\mathrm{ndeg} \le \deg \le 9$. |
| Triangle finding total | \(3\) putative | Upper: $\sum_{\{a,b,c\}}x_{ab}x_{bc}x_{ca}$ is a sum of non-negative terms, positive exactly on the graphs with a triangle, so $\mathrm{ndeg}\le\mathrm{C}^1=3$. Lower: fix one triple free and every other edge to $0$; a multilinear polynomial in three variables vanishing on the other seven points must be a multiple of $x_1x_2x_3$, and nondeterministic degree does not increase under restriction. deWolf03 |
| Ordered search partial | \(1\) putative | A linear form suffices: pick $c_i$ so that $\sum_{i>k}c_i$ is $0$ for even $k$ and $1$ for odd $k$ (successive differences are $\pm1$), giving $p$ nonzero exactly on the $1$-inputs of the promise. Nondeterministic degree is defined on the domain only, so nothing off the chain constrains $p$; and $\mathrm{ndeg}\ge1$ since the function is nonconstant. |
| Inner product mod 2 total | \(\Theta(n)\) putative | Upper: $p = 1 - \prod_{i}(1-2x_iy_i) = 1-(-1)^{x\cdot y}$ is nonzero exactly on $\mathrm{IP}^{-1}(1)$, degree $n$. Lower: any nondeterministic polynomial $p$ gives a sign-representing one -- $q(x) := \delta - p(x)^2$ is $>0$ on $f^{-1}(0)$ and $<0$ on $f^{-1}(1)$ for any $\delta$ below the least positive value of $p^2$ -- so $\mathrm{sdeg}(f) \le 2\,\mathrm{ndeg}(f)$ always, and $\mathrm{sdeg} = \Theta(n)$ here. Bentness leaves no room for a nondeterministic shortcut. |
| Minsky-Papert one-in-a-box total | \(m = N^{1/3}\) putative | Upper: $\mathrm{ndeg} \le \mathrm{C}^1 = m$. Lower: planting a $0$ in all but one bit of each box restricts MP to $\mathrm{AND}_m$, and a polynomial nonzero exactly at $1^m$ must be a multiple of $\prod_i x_i$, so $\mathrm{ndeg}(\mathrm{AND}_m) = m$; restrictions do not increase $\mathrm{ndeg}$. |
| Sink of a tournament total | \(m-1 = \Theta(\sqrt N)\) putative | Upper: $\mathrm{ndeg} \le \mathrm{C}^1 = m-1$. Lower: fix a sink-free tournament on $V \setminus \{v\}$ and leave the $m-1$ edges at $v$ free; the restriction is $\mathrm{AND}_{m-1}$, whose nondeterministic degree is $m-1$ (a polynomial nonzero exactly at $1^k$ is a multiple of $\prod_i x_i$), and restrictions do not increase $\mathrm{ndeg}$. |
| Scorpion graphs total | \(\Theta(m)\) putative | Upper: for $m \ge 5$ the property is a disjoint union of $m(m-1)(m-2)$ subcubes of codimension $3m-6$, and the sum of their indicator monomial products is nonzero exactly on the scorpions, so $\mathrm{ndeg} \le 3m-6$. Lower: the restriction of the \(\mathrm{Q}_{0}(f)\) entry turns $\mathrm{SCORP}_m$ into $\mathrm{AND}_{m-3}$, a polynomial nonzero exactly at $1^k$ is a multiple of $\prod_i x_i$, and restrictions never increase $\mathrm{ndeg}$, so $\mathrm{ndeg} \ge m-3$. |
| Graph connectivity total | \(m-1\) putative | Exactly. Upper: the spanning-tree generating polynomial $\tau(G) = \sum_{T}\prod_{e \in T}x_e$ (the reduced Laplacian determinant of the matrix-tree theorem) is multilinear of degree $m-1$ and is nonzero precisely when $G$ is connected, all its terms being non-negative. Lower: fix a spanning tree's $m-1$ pairs free and all other pairs absent; the restriction is $\mathrm{AND}_{m-1}$, a polynomial nonzero exactly at $1^{k}$ is a multiple of $\prod_i x_i$, and restrictions never increase $\mathrm{ndeg}$. So the nondeterministic degree of connectivity is $\Theta(\sqrt N)$, a quadratic drop from $\deg = N$. |