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
- \(\mathrm{R}_{\varepsilon}(f)\) $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ for Boolean-valued $f$: the canonical answer is forced, so reproducibility is free GGR13
- \(\mathrm{R}_{\varepsilon}(f)\) $\mathrm{psD}(f) = \Theta(\mathrm{R}(f))$ on the promise as well -- the collapse only needs the answer to be unique GGR13
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.
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 | \(\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)$. |