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 {\em unary}\/ instances (a.k.a explicit construction problems).
In particular, we prove the following results.

\begin{itemize}
\item
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.
\item
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.

\item
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$.
\end{itemize}
We discuss the gap between the former hypotheses and the result provided by Chen, Lu, Oliveira, Ren, and Santhanam (FOCS23).