TR12-101 Authors: Oded Goldreich, Shafi Goldwasser, Dana Ron

Publication: 10th August 2012 17:52

Downloads: 3813

Keywords:

We study the possibilities and limitations

of pseudodeterministic algorithms,

a notion put forward by Gat and Goldwasser (2011).

These are probabilistic algorithms that solve search problems

such that on each input, with high probability, they output

the same solution, which may be thought of as a canonical solution.

We consider both the standard setting of (probabilistic) polynomial-time

algorithms and the setting of (probabilistic) sublinear-time algorithms.

Some of our results are outlined next.

In the standard setting, we show that

pseudodeterminstic algorithms are more powerful

than deterministic algorithms if and only if $P \neq BPP$,

but are weaker than general probabilistic algorithms.

In the sublinear-time setting,

we show that if a search problem has a pseudodeterminstic algorithm

of query complexity $q$, then this problem can be solved deterministically

making $O(q^4)$ queries. This refers to total search problems.

In contrast, for several natural promise search problems,

we present pseudodeterministic algorithms that are much more efficient

than their deterministic counterparts.