Complexity theoretic implications of pseudodeterministic algorithms for PPT-search problems

Webpage for a paper by Oded Goldreich and Roei Tell

Abstract

Pseudodeterministic algorithms are probabilistic algorithms that solve search problems but do so by always providing the same (``canonical'') solution to a given instance, except with small probability. While the complexity theoretic implications of pseudodeterministic algorithms were explored in the past, we suggest to conduct this exploration within the framework of the recently defined class of PPT-search problems. Specifically, we use this framework in order to re-formulate some known observations as well as present some new results. In particular, as observed in the past, the difference between general probabilistic polynomial-time algorithms and pseudodeterministic ones is reflected in the difference between promise-$\BPP$ and $\BPP$. We make this connection stronger by showing that every PPT-search problem has a pseudodeterministic polynomial-time algorithm if and only if every decisional problem in promise-$\BPP$ can be extended to a problem in $\BPP$. Our main focus is on the class of PPT-search problems with unary instances (a.k.a explicit construction problems). In particular, we prove the following results.

• Pseudodeterministic polynomial-time algorithms exist for all unary PPT-search problems if and only if there exist functions that are computable in probabilistic exponential-time but are hard to learn in significantly smaller exponential time. The underlying technique is used in order to identify the pseudodeterministic construction of a pseudorandom-set as ``universal'' for the class of unary PPT-search problems.
• The existence of pseudodeterministic polynomial-time algorithms for all unary PPT-search problems implies that every unary problem in promise-$\BPP$ can be extended to a (unary) problem in $\BPP$. As a corollary, we obtain an alternative proof for a result of Lu, Oliveira, and Santhanam (STOC21), asserting that such algorithms imply a BPtime hierarchy.
• The existence of pseudodeterministic polynomial-time algorithms for a subclass of the unary PPT-search problems (wherein solutions can be verified deterministically) implies results akin to a BPtime hierarchy. For example, it implies that RTime(p) is not contained in BPtime(q), for any polynomial $p$ and a related polynomial $q$.

Material available on-line

• First version posted: Feb 2025.
• Revisions: none yet.