We study the possibilities and limitationsof pseudodeterministic algorithms,a notion put forward by Gat and Goldwasser (2011).These are probabilistic algorithms that solve search problemssuch that on each input, with high probability, they outputthe same solution, which may be thought of as a canonical solution.We consider both the standard setting of (probabilistic) polynomial-timealgorithms and the setting of (probabilistic) sublinear-time algorithms.Some of our results are outlined next.

In the standard setting, we show thatpseudodeterminstic algorithms are more powerfulthan deterministic algorithms if and only if P=BPP ,but are weaker than general probabilistic algorithms.In the sublinear-time setting,we show that if a search problem has a pseudodeterminstic algorithmof query complexity q, then this problem can be solved deterministicallymaking O(q4) queries. This refers to total search problems.In contrast, for several natural promise search problems,we present pseudodeterministic algorithms that are much more efficientthan their deterministic counterparts.