Q The Query Complexity Zoo
\(\mathrm{Find1}_{\ge n/2}\)

FIND-1 under a density promise

The cleanest D-vs-R relational separation: $\mathrm{R}=O(1)$, $\mathrm{D}=n/2+1$.

relation relational arity: $n$ bits

Description

Promise $|x| \ge n/2$; output any $i$ with $x_i = 1$. Sampling a single random index succeeds with probability $\ge 1/2$, so $\mathrm{R}=O(1)$; but an adversary can answer $0$ to a deterministic algorithm's first $n/2$ queries.

Measure values

MeasureValueNotes
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity \(O(1)\)
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity \(O(1)\) Zero error too: the algorithm verifies its own output, which is exactly why $\mathrm{R}_0=\Theta(\mathrm{R})$ for relations.
\(\mathrm{D}(f)\) Deterministic query complexity \(n/2+1\)
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity \(\Theta(n)\)· Reproducibility is what costs: cf. ApproxHW. The $\Omega(n)$ side is the content; the $O(n)$ side is $\mathrm{psD} \le \mathrm{D}$.
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity \(\Theta(1)\) A dense search problem: one uniform sample already works, so quantum has nothing to speed up. $\mathrm{Q} \le \mathrm{R} = O(1)$.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity \(\Theta(1)\) $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity \(\Theta(1)\) putative Sampling is already non-adaptive: read $10$ uniformly random positions and output any that is $1$.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity \(n/2+1\) putative A fixed set of $n/2+1$ positions must contain a $1$ (a promise input has at most $n/2$ zeros), and a fixed set of $n/2$ positions can be entirely zero. So adaptivity is worth nothing on the deterministic side either -- all the power is in the coins.
\(\mathrm{C}(f)\) Certificate complexity \(1\) putative One queried $1$ certifies its own index as a valid output, at every input. So $\mathrm{C} = 1$ against $\mathrm{D} = n/2+1$: for relations, certificate complexity does not bound deterministic complexity at all, because knowing that a short certificate exists does not tell you where to look.
\(\mathrm{C}^1(f)\) 1-certificate complexity \(1\) putative Same certificate.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound \(\Theta(1)\) Sandwiched between $\mathrm{Q} = \Theta(1)$ and $\mathrm{R} = O(1)$.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity \(\Theta(1)\) Sandwiched between $\mathrm{Q}$ and $\mathrm{R} = O(1)$.
\(\mathrm{cbs}(S)\) Critical block sensitivity \(0\) putative Vacuously: \(\mathrm{cbs}(S)\) maximises over critical inputs, those with a unique valid answer, and this problem has none. A promise input has $|x| \ge n/2 \ge 2$ ones for $n \ge 4$, so every input admits at least two answers and the max is over the empty set. So critical block sensitivity -- the standard route to relational lower bounds -- says nothing whatever about a problem with $\mathrm{D} = n/2+1$. Contrast \(\mathrm{Search}(\varphi)\) and \(\mathrm{SEARCH}_n\), where the unique-answer inputs are exactly what carries the hardness.
\(\mathrm{rank}(f)\) Decision tree rank \(1\) putative The optimal tree "query $x_1, x_2, \dots$ and stop at the first $1$" is a caterpillar, so its rank is $1$; and rank $0$ means a constant answer. A Delayer in the Prover--Delayer game scores nothing here because the Prover's query is always one the adversary is happy to answer $0$.
\(\mathrm{DTsize}(f)\) Decision tree size \(\Theta(n)\) putative The caterpillar has one leaf per stopping point, so $O(n)$; and a tree of depth $d$ has more than $d$ leaves, so $\Omega(n)$ by $\mathrm{D} = n/2+1$. Unlike \(\mathrm{ApproxHW}\) and \(\mathrm{Search}(\varphi)\), the deterministic hardness here is entirely depth and not at all size.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity \(\Theta(1)\) putative Sample $O(1)$ random positions and read each $O(1)$ times to drive the noise below any constant: the promise means a random position is $1$ with probability $\ge 1/2$, so a constant number of noisy reads suffices.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity \(\Theta(1)\) At most $\mathrm{N}_p = \Theta(1)$ (a noisy quantum algorithm can simulate the classical one), and at least $\mathrm{Q} = \Theta(1)$.
\(\mathrm{CA}(f)\) Classical adversary bound \(\Theta(1)\) The classical adversary bound is a lower bound on $\mathrm{R}$, which is $O(1)$ here; and it is at least a constant for any non-trivial problem. So the relational adversary, which was designed for search problems, is powerless against \(\mathrm{Find1}_{\ge n/2}\) -- correctly so, since $\mathrm{R} = O(1)$.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree \(\Theta(1)\) Squeezed by $\mathrm{cjdeg} \le \mathrm{R} = O(1)$ and by $\mathrm{cjdeg} \ge 1$ for a non-constant problem.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound \(O(1)\) From $\mathrm{prt} \le 2\mathrm{R} = O(1)$.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound \(O(1)\) From $\overline{\mathrm{prt}} \le \mathrm{prt} = O(1)$.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity \(\Theta(1)\) The output is self-verifying -- the algorithm only ever names an index it has seen to be $1$ -- so the bounded-error algorithm is already zero-error: $\mathrm{Q}_0 \le \mathrm{R}_0 = O(1)$. Contrast \(\mathrm{SEARCH}_n\), where $\mathrm{Q}_0 = n$ because the all-zero input has no witness; the density promise removes that input.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity \(n/2+1\)· putative Exactness is as expensive as determinism. A quantum algorithm that must output a valid index with certainty after $q$ queries still has to have queried a $1$ in every branch of its computation, and the adversary that answers $0$ to the first $n/2$ distinct positions keeps a promise-consistent input alive; and $\mathrm{Q}_E \le \mathrm{D} = n/2+1$. So the whole $\Theta(n)$-to-$O(1)$ collapse here is a bounded-error effect.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound \(\Theta(1)\) A lower bound on $\mathrm{Q} = \Theta(1)$, and at least $1$.
\(\mathrm{MAdv}(f)\) Multiplicative adversary \(\Theta(1)\) Sandwiched: $\mathrm{Adv}^{\pm} \le \mathrm{MAdv} \le \mathrm{Q}$, both $\Theta(1)$.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm \(\Theta(1)\) $\gamma_2 = \Theta(\mathrm{Q}) = \Theta(1)$.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity \(1\) putative Equal to $\mathrm{C}$: the same one-bit certificate works at every input, since the promise guarantees a $1$ exists.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity \(\Theta(1)\) At most $\mathrm{D}^\mu = \Theta(1)$ for every $\mu$, hence in particular for product ones; and at least one query.
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity \(\Theta(1)\) At most $\mathrm{R} = O(1)$, and at least $1$: buying bias cannot help a problem that is already solved by one full-strength query.
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity \(\Theta(1)\) Squeezed: $\mathrm{noisyR} = \Theta(1) \le \mathrm{noisyR}^{\mathrm{na}} \le \mathrm{R}^{\mathrm{na}} = \Theta(1)$. Against $\mathrm{psD} = \Theta(n)$ this is an unbounded gap: committing to a canonical answer is what is expensive, not adaptivity or query strength.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity \(\Theta(n)\) putative At least $n/2$, so parity queries are as useless as ordinary ones. Answer $0$ to every query; after $q$ queries the consistent inputs form the linear space $W^{\perp}$, $\dim = n-q$, where $W$ is the span of the queried sets. A leaf that outputs $i$ must have $x_i = 1$ throughout $W^{\perp} \cap \{|x| \ge n/2\}$, but $V = W^{\perp} \cap \{x_i = 0\}$ has dimension $\ge n-q-1$, and any subspace of dimension $d$ contains a vector of weight $\ge d$ (sum the reduced-echelon basis: it is $1$ on all $d$ pivots). For $q \le n/2 - 1$ that vector satisfies the promise and refutes the leaf. And $\mathrm{D}^{\oplus} \le \mathrm{D} = n/2+1$. Against $\mathrm{R} = O(1)$ this is the same unbounded gap as for $\mathrm{D}$.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity \(\Theta(1)\) Squeezed: $\mathrm{R} \le \mathrm{R}^1 \le \mathrm{R}_0 = O(1)$. The promise $|x| \ge n/2$ means a random probe both finds and certifies a $1$, so never emitting an invalid output costs nothing extra -- in sharp contrast to \(\mathrm{SEARCH}_n\).
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity \(\Theta(1)\) At most $\mathrm{Q} = \Theta(1)$, and at least $1$: there is nothing for postselection to buy.

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. 74 in total, strongest first.

… and 60 more, all of them visible in the matrix (widen it to all measures) and on the pair pages.

Separations it witnesses

Cited as a witness by