Q The Query Complexity Zoo
\(\mathrm{R}_{\mathrm{RP}}(f)\)

One-sided randomized queries with certain rejection

Negative inputs always reject; positive inputs accept with probability at least 2/3.

also written: R_1 in Ambainis–Iraids–Kokainis 2026, RP query complexity

Definition

The minimum worst-case query count of a randomized algorithm that always rejects $0$-inputs and accepts each $1$-input with probability at least $2/3$. This is $\mathrm{R}_1$ in [AIK26, Section 2.1]. The zoo's existing \(\mathrm{R}^{1}(f)\) fixes the other error convention (certain acceptance on positive inputs); keeping separate ids prevents attaching the one-sided algorithm to the wrong function.

Basic facts

  • $\mathrm{R}\le\mathrm{R}_{\mathrm{RP}}=O(\mathrm{R}_0)$.
  • \(\mathrm{AIKuD}\) has $\mathrm{C}=\Theta(n^2)$ and $\mathrm{R}_{\mathrm{RP}}=\Theta(n)$ [AIK26, Theorem 2.2].

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{R}_{\mathrm{RP}}(f)\). “\(\mathrm{R}_{\mathrm{RP}}(f)\) in terms of it” is the pair with \(\mathrm{R}_{\mathrm{RP}}(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.

Other measure \(\mathrm{R}_{\mathrm{RP}}(f)\) in terms of it It in terms of \(\mathrm{R}_{\mathrm{RP}}(f)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,2 partial1,? derived open pair → total1,1 partial1,1 open pair →
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity total1,2 partial1,? derived open pair → total1,2 partial1,? derived open pair →
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity total1,1 partial1,1 open pair → total2,2 partial2,? derived open pair →
\(\mathrm{C}(f)\) Certificate complexity total2,2 partial∞ derived open pair → total2,2 partial2,? open pair →
\(\mathrm{C}^1(f)\) 1-certificate complexity total∞ partial∞ derived open pair → total1,2 partial1,? derived open pair →

The 5 above are this entry’s hand-picked neighbours; the other 88 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(n)\) The randomized lower bound Θ(n) and the deterministic upper bound n squeeze this one-sided variant on the standard family. AIK26
AND total \(\Theta(n)\) The randomized lower bound Θ(n) and the deterministic upper bound n squeeze this one-sided variant on the standard family. AIK26
PARITY total \(\Theta(n)\) The randomized lower bound Θ(n) and the deterministic upper bound n squeeze this one-sided variant on the standard family. AIK26
MAJORITY total \(\Theta(n)\) The randomized lower bound Θ(n) and the deterministic upper bound n squeeze this one-sided variant on the standard family. AIK26
Ambainis–Iraids–Kokainis unambiguous DNF total \(\Theta(n)\) Theorem 2.2; accepts only after a term is verified. AIK26