Q The Query Complexity Zoo

Total functions, partial functions, and relations

The single most important distinction in this zoo: almost every polynomial relation is a theorem about total Boolean functions only.

Three kinds of computational problem appear in query complexity, and the zoo keeps them strictly apart.

Total function

$f : \{0,1\}^n \to \{0,1\}$. Every input is legal, every input has exactly one right answer. This is the setting of essentially every polynomial relation in the literature. When a paper says "$\mathrm{D}(f) = O(\mathrm{R}(f)^3)$" with no qualification, it means total $f$.

Partial function (promise problem)

$f : \mathrm{Dom}(f) \to \{0,1\}$ with $\mathrm{Dom}(f) \subseteq \{0,1\}^n$. The algorithm may behave arbitrarily off the promise. Almost every polynomial relation fails, usually spectacularly:

relation total partial
$\mathrm{D}$ vs $\mathrm{R}$ $\mathrm{D}=O(\mathrm{R}^3)$ unbounded (\(\mathrm{Find1}_{\ge n/2}\))
$\mathrm{R}$ vs $\mathrm{Q}$ $\mathrm{R}=O(\mathrm{Q}^4)$ unbounded (\(\mathrm{forr}\), \(\mathrm{SIMON}_n\))
$\mathrm{Q}$ vs $\widetilde{\deg}$ polynomial exponential [AmbainisBelovs23]
$\mathrm{D}$ vs $\mathrm{s}$ $\mathrm{D}\le\mathrm{s}^4$ unbounded

What does survive: the trivial chain $\mathrm{Q}\le\mathrm{R}\le\mathrm{R}_0\le\mathrm{D}$, the polynomial method ($\widetilde{\deg}\le 2\mathrm{Q}$, $\widetilde{\deg}\le\mathrm{R}$), and the general adversary characterisation $\mathrm{Q}=\Theta(\mathrm{Adv}^{\pm})$. These never used totality.

Why do the combinatorial measures die? Because $\mathrm{s}$, $\mathrm{bs}$, $\mathrm{C}$ and friends all measure local structure of the hypercube, and a promise deletes most of the hypercube. A single promise can make every input have an $O(1)$-size certificate while leaving the problem maximally hard.

Relation / search problem

$S \subseteq \{0,1\}^n \times \mathcal{O}$ where every $x$ has at least one valid output. The algorithm must output some $o$ with $(x,o)\in S$. A total search problem is the query analogue of $\mathsf{TFNP}$.

Which measures still make sense?

  • Fine: $\mathrm{D}$, $\mathrm{R}$, $\mathrm{R}_0$, $\mathrm{Q}$, $\mathrm{Adv}^{\pm}$, $\mathrm{prt}$, $\mathrm{cjdeg}$, $\overline{\mathrm{prt}}$, $\mathrm{DTsize}$.
  • Only meaningful here: \(\mathrm{psD}(S)\) (pseudo-determinism) -- for a function there is only one correct answer, so $\mathrm{psD}=\mathrm{R}$; for a search problem, committing to a canonical answer can be exponentially harder [CDM23].
  • Awkward or undefined: anything defined through $f^{-1}(0)$ and $f^{-1}(1)$ -- $\mathrm{s}$, $\mathrm{bs}$, $\mathrm{C}^0/\mathrm{C}^1$, $\deg$, $\widetilde{\deg}$ (one can define these via the output relation but the standard theorems do not apply). Approximate degree is usually defined for search problems as the minimum degree of a "conical junta"- style certificate; see \(\mathrm{cjdeg}_{\varepsilon}(f)\).
  • Collapses: $\mathrm{R}_0$ vs $\mathrm{R}$ largely collapses when outputs are cheaply verifiable.

Total search problems are much closer to partial functions than to total functions: [BenDavidKundu24search] give explicit conversions in both directions, and use them to transport exponential separations back and forth.