Q The Query Complexity Zoo
\(\mathrm{psD}(S)\)

Pseudo-deterministic query complexity

Randomized cost of a search algorithm that must output the same canonical answer with high probability on every input.

also written: pseudodeterministic decision tree complexity, reproducible randomized complexity

Definition

For a relation $S \subseteq \{0,1\}^n \times \mathcal{O}$, a pseudo-deterministic algorithm is a randomized decision tree $A$ together with a canonical solution function $s : \{0,1\}^n \to \mathcal{O}$ with $(x, s(x)) \in S$, such that $$\Pr[A(x) = s(x)] \ \ge\ 2/3 \quad\text{for every } x .$$ $\mathrm{psD}(S)$ is the least worst-case cost of such an $A$. It interpolates between $\mathrm{R}$ and $\mathrm{D}$: a deterministic algorithm is trivially pseudo-deterministic, and a pseudo-deterministic algorithm is randomized. This is the measure that makes the relational setting interesting: for Boolean-valued $f$ it collapses, $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$, because the canonical answer is forced.

Basic facts

  • $\mathrm{R}(S) \le \mathrm{psD}(S) \le \mathrm{D}(S)$.
  • $\mathrm{D}(S) = O(\mathrm{psD}(S)^3)$ for total search problems [CDM23], improving the quartic bound of [GGR13].
  • $\mathrm{R}$ and $\mathrm{psD}$ are exponentially separated: for the approximate-Hamming-weight relation $\mathrm{ApproxHW}$, $\mathrm{R} = O(1)$ while $\mathrm{psD} = \Omega(n)$ [CDM23]; and $\mathrm{psD}(\mathrm{SearchCNF}) = \Omega(n^{1/3})$ for random $k$-CNFs [CDM23], $\Omega(\sqrt{n})$ in the setting of [GIPS21].
  • In the zero-error average-case setting, deterministic, randomized and pseudo-deterministic complexity all coincide [GIPS21].

Equivalent / near-equivalent measures

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{psD}(S)\). “\(\mathrm{psD}(S)\) in terms of it” is the pair with \(\mathrm{psD}(S)\) 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{psD}(S)\) in terms of it It in terms of \(\mathrm{psD}(S)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 relation∞ open pair → total1,1 partial1,1 relation1,1 derived open pair →
\(\mathrm{D}(f)\) Deterministic query complexity total1,1 partial1,1 relation1,1 open pair → total2,3 partial∞ relation1.127,3 open pair →
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity total1,1 partial1,1 relation∞ derived open pair → total2,2 partial∞ relation1,3 derived open pair →
\(\mathrm{cbs}(S)\) Critical block sensitivity total2,3 partial∞ relation∞ derived open pair → total1,1 partial1,1 relation1,1 derived open pair →

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

Known values

FunctionValueNotes
OR total \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$. Contrast the relation \(\mathrm{ApproxHW}\), where $\mathrm{R} = O(1)$ but $\mathrm{psD} = \Omega(n)$ [CDM23]. CDM23
AND total \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$. CDM23
PARITY total \(n\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$, and $\mathrm{R} = \mathrm{D} = n$ here, so all three of $\mathrm{R}$, $\mathrm{psD}$ and $\mathrm{D}$ coincide exactly. CDM23
MAJORITY total \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$. CDM23
Threshold total \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$, uniformly in $k$. CDM23
Symmetric functions (general) total \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$ by the \(\mathrm{R}_{\varepsilon}(f)\) line. CDM23
EXACT-HALF total \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$. CDM23
ODD-MAX-BIT total \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$. CDM23
ADDRESS / multiplexer total \(\Theta(k)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(k)$. CDM23
Binary tree navigation total \(\Theta(k)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(k)$. CDM23
TRIBES total \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ $= \Theta(n)$. CDM23
AND-OR tree (depth 2) total \(\Theta(n^2) = \Theta(N)\) For a Boolean-valued function pseudo-determinism is free -- the canonical answer is forced to be $f(x)$ -- so $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$, and $\mathrm{R} = \Theta(n^2)$ here.
NAND tree (balanced AND-OR formula) total \(\Theta\!\big(N^{\,0.753\ldots}\big)\) For a Boolean-valued function the canonical answer is forced to be $f(x)$, so pseudo-determinism is free: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$.
Recursive MAJORITY-of-3 total \(\Omega(2.59^{\,d}),\ O(1.007\cdot 2.64944^{\,d})\) For a Boolean-valued function the canonical answer is forced to be $f(x)$, so pseudo-determinism is free: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$, and this is the recorded \(\mathrm{R}_{\varepsilon}(f)\) window verbatim.
Kushilevitz's function (iterated) total \(\Theta(N)\) For a Boolean-valued function the canonical answer is forced to be $f(x)$, so pseudo-determinism is free: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f)) = \Theta(N)$.
Rubinstein's function total \(\Theta(N)\) For a Boolean-valued function the canonical answer is forced to be $f(x)$, so pseudo-determinism is free: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f)) = \Theta(N)$.
Ambainis-Sun function total \(\Theta(N)\) For a Boolean-valued function the canonical answer is forced to be $f(x)$, so pseudo-determinism is free: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f)) = \Theta(N)$.
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) For a Boolean-valued function the canonical answer is forced to be $f(x)$, so pseudo-determinism is free: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f)) = \Theta(n^2)$.
Meiburg's tournament-subcube function total \(\ge 14011^{\,d}\) putative For a Boolean-valued function the canonical answer is forced to be $f(x)$, so pseudo-determinism is free: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f)) = \Omega(\mathrm{bs})$.
Pointer functions total \(\widetilde O(\sqrt n)\) Variant $g_{m,m}$: for a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\widetilde O(\sqrt n)$.
Cheat-sheet functions total \(\widetilde\Theta(n)\) For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\widetilde\Theta(n)$.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\widetilde\Omega(n^3)$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3})\) For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\widetilde\Omega(n^{4/3})$.
Gilmer-Saks-Srinivasan functions total \(\Theta(n^2)\) For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\Theta(n^2)$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n)\) For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\widetilde\Omega(\sqrt n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{2/3})\) For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=\widetilde\Theta(n^{2/3})$.
Ambainis' exact-quantum function total \(3^d\) For a Boolean function the canonical solution is forced to be $f$ itself, so $\mathrm{psD}=\mathrm{R}=3^d$.
FORRELATION partial \(\widetilde\Theta(\sqrt n)\) Degenerate on a partial Boolean function: there is only one correct answer, so the canonical solution function is forced to be $f$ itself and reproducibility is free. Hence $\mathrm{psD} = \Theta(\mathrm{R}) = \widetilde\Theta(\sqrt n)$ -- see the \(\mathrm{psD}(S)\) entry.
k-FORRELATION partial \(\widetilde\Theta\!\big(n^{1-1/k}\big)\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R})$, since the canonical solution function is forced to be $f$ itself.
Simon's problem partial \(\Theta(2^{n/2})\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(2^{n/2})$, since the decision version has a unique correct answer.
Deutsch-Jozsa partial \(\Theta(1)\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(1)$.
Bernstein-Vazirani partial \(\Theta(n)\) Degenerate: the secret $s$ is unique, so there is only one valid output and a pseudo-deterministic algorithm is just a randomized one. Hence $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(n)$.
Marked bit partial \(\Theta(n)\) Degenerate for Boolean functions: there is a single correct output, so the canonical answer is forced and $\mathrm{psD}(f) = \Theta(\mathrm{R}(f)) = \Theta(n)$. CDM23
Dense marked bit partial \(\Theta(1)\) Degenerate for Boolean functions: $\mathrm{psD}(f) = \Theta(\mathrm{R}(f)) = \Theta(1)$. CDM23
Unstructured search (relation) relation \(\Theta(n)\) putative Sandwiched between $\mathrm{R} = \Theta(n)$ and $\mathrm{D} = n$, so the sandwich alone settles it -- no separate pseudo-determinism argument is needed. Contrast \(\mathrm{ApproxHW}\) and \(\mathrm{Find1}_{\ge n/2}\), where $\mathrm{R}$ is small and demanding a canonical answer is what makes the problem hard.
FIND-1 under a density promise relation \(\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}$.
Approximate Hamming weight relation \(\Theta(n)\) The $\Omega(n)$ side is the theorem; $\mathrm{psD} \le \mathrm{D} = O(n)$ closes it. CDM23 GIPS21
SearchCNF relation \(\Omega(n^{1/3})\) $\Omega(\sqrt n)$ in the related setting of [GIPS21]; also $\exp(\widetilde\Omega(n^{1/4}))$ in pseudo-deterministic decision-tree size. CDM23
Gap-Majority partial \(\Theta(\min(n, 1/\delta^2))\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R})$.
Gap-Majority at constant gap partial \(\Theta(1)\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R})$.
Approximate index partial \(\Theta(\sqrt{k\log k})\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(\sqrt{k\log k})$.
Collision problem partial \(\Theta(\sqrt n)\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(\sqrt n)$. (The search version -- find a collision -- is the one where pseudo-determinism bites; the decision version has a unique answer.)
Element distinctness total \(\Theta(n)\) Degenerate on a total function: only one correct answer, so $\mathrm{psD} = \Theta(\mathrm{R}) = \Theta(n)$.
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) Degenerate on a partial Boolean function: $\mathrm{psD} = \Theta(\mathrm{R}) = \Omega(n^{1/3})$, with $\mathrm{psD} \le \mathrm{D} = O(n)$ above.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) At least $\mathrm{R}$, since $\mathrm{R} \le \mathrm{psD}$.
Yamakawa-Zhandry problem relation \(2^{\Omega(n)}\) At least $\mathrm{R} = 2^{\Omega(n)}$, since $\mathrm{R} \le \mathrm{psD}$. Pseudo-determinism costs nothing extra here in any interesting sense -- the point is the contrast with $\mathrm{Q} = \mathrm{poly}(n)$, which makes this the strongest form of quantum advantage on record for a search problem: exponential, verifiable, and against the pseudo-deterministic classical model.
Welded trees relation \(\tilde\Theta(2^{n/2})\) Squeezed by $\mathrm{R} \le \mathrm{psD} \le \mathrm{D}$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and here $\mathrm{R}$ and $\mathrm{D}$ already agree to within $n^2$. Pseudo-determinism costs nothing because the answer is unique to begin with: there is only one solution function, so the canonical-answer requirement is vacuous.
Local search on the hypercube relation \(\Omega(2^{n/2}\sqrt n),\ O(2^n/\sqrt n)\) Only the generic $\mathrm{R} \le \mathrm{psD} \le \mathrm{D}$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and here the two ends are quadratically apart, so this is one of the natural places to look for a genuine pseudo-deterministic separation: a randomized algorithm may return any local minimum, but committing in advance to which one looks much closer to the deterministic problem of finding a canonical minimum.
Local search on the grid relation \(\Omega(k^{d/2}),\ O(k^{d-1})\ (d \ge 4)\) Only the generic $\mathrm{R} \le \mathrm{psD} \le \mathrm{D}$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). The window is a factor $k^{d/2-1}$ wide, and unlike \(\mathrm{LS}(\{0,1\}^n)\) it stays wide for every fixed $d \ge 4$, so the grid is the cleaner family to ask the pseudo-deterministic question on: is there a canonical local minimum findable in $\tilde O(k^{d/2})$ randomized queries?
Fourier fishing relation \(\Omega(N/\log N),\ O(N)\) Only the generic $\mathrm{R} \le \mathrm{psD} \le \mathrm{D}$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)), and the window is the same $\log N$ that is open for $\mathrm{R}$. Pseudo-determinism cannot help much here because $\mathrm{R}_0 = \Theta(N)$ already pins the top of the range.
Tseitin search on an expander relation \(\Theta(n)\) putative At least $\mathrm{R} = \Theta(n)$ and at most $\mathrm{D} = \Theta(n)$, so pseudo-determinism is free here. Contrast \(\mathrm{Search}(\varphi)\) and \(\mathrm{ApproxHW}\), where it is exactly the expensive part.
Inner product mod 2 total \(\Theta(n)\) For a Boolean function the canonical answer is forced, so $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)); here $\mathrm{R} = \Theta(n)$.
Minsky-Papert one-in-a-box total \(\Theta(m^3) = \Theta(N)\) For a Boolean function the canonical answer is forced, so $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)); here $\mathrm{R} = \Theta(N)$.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) For a Boolean function the canonical answer is forced, so $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)).
Scorpion graphs total \(\Theta(m)\) For a Boolean function the canonical answer is forced, so $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)); here $\mathrm{R} = \Theta(m)$.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) For a Boolean function the canonical answer is forced, so $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)); here $\mathrm{R} = \Theta(m^2)$.