13
$\begingroup$

Definition. A randomized algorithm for a search problem is pseudodeterministic if it produces a fixed canonical solution to the search problem with high probability.

Question. The notion of a pseudodeterministic algorithm is simple enough, but I cannot think of a simple one. A search on the web only reveals theoretical papers that don't seem to straightforwardly show one. Can you show me a simple one so that I can see that it is possible (to exist)?

$\endgroup$
5
  • $\begingroup$ In theory, I can't distinguish pseudodeterministic algorithms from Las Vegas algorithms. Noting that Las Vegas algorithms are the function class version of ZPP, and one definition of ZPP is a decision version of your definition. So, is there a difference in theory from Las Vegas algorithms, or only in practice (i.e. one definition emphasizes randomized runtime, the other randomized correctness). $\endgroup$
    – usul
    Jul 20, 2023 at 2:15
  • $\begingroup$ Maybe I should explain more directly: if we have a Las Vegas algorithm (randomized runtime, always correct), we can turn it into an algorithm that is correct with high probability and has a deterministic runtime by truncating the computation after a fixed multiple of the expected runtime. If we have a pseudodeterministic algorithm, and we can check correctness of solutions efficiently, then we can turn it into a Las Vegas algorithm by switching to exhaustive search whenever it's incorrect. $\endgroup$
    – usul
    Jul 20, 2023 at 2:27
  • $\begingroup$ Good question. Your notice of Las Vegas algorithms makes me think of randomized Quicksort as a pseudodeterministic algorithm because randomized Quicksort makes use of random bits, always produces a fixed sorted list as output with (very) high probability. I also say that sorting is a search problem in which the universe of search is every permutation of the list of elements to be sorted. In other words, I'm also unable to distinguish pseudodeterministic from Las Vegas methods. $\endgroup$
    – user69687
    Jul 23, 2023 at 1:49
  • $\begingroup$ One thought that comes to mind is that randomized Quicksort is both a pseudodeterministic algorithm and a Las Vegas algorithm. In other words, Las Vegas is a larger set that contains pseudodeterministic algorithms. Although randomized Quicksort always produces a fixed sorted list as output, this is not required by the definition of a Las Vegas algorithm. $\endgroup$
    – user69687
    Jul 23, 2023 at 2:01
  • $\begingroup$ maybe problems that are not in NP $\inf$ coNP so they are not easy to turn into smallest answer versions (which have unique answers). $\endgroup$
    – Kaveh
    Jul 25, 2023 at 0:43

2 Answers 2

5
$\begingroup$

The Tonelli–Shanks algorithm for computing square roots modulo primes.

More generally, factorization of polynomials over finite fields using the Cantor–Zassenhaus algorithm.

Both can be made pseudodeterministic by canonizing the result in a suitable way (e.g., for square roots, output the unique square root in $\{0,\dots,(p-1)/2\}$; for factorization, require the factors to be monic, and output them in some sort of lexicographic order).

$\endgroup$
6
  • 2
    $\begingroup$ Though your answer is technically correct, I think these are not convincing examples for pseudo-deterministic algorithms, since in both cases, the algorithm is actually computing the only solution to the problem. (For square roots over $ℤ/pℤ$, once you have one, you get the other one; and unique factorization of polynomials over finite fields is, morally, unique.) This is very different from the recent pseudo-deterministic algorithm to compute an $n$-bit prime number. $\endgroup$
    – Bruno
    Jul 19, 2023 at 9:34
  • $\begingroup$ So what? Why should a good example be similar to some particular recent algorithm? This reasoning does not make sense to me. These are standard algorithms that are reasonably simple, solve natural problems with practical applications, and they are pesudodeterministic, while no deterministic algorithms are known. $\endgroup$ Jul 19, 2023 at 9:46
  • $\begingroup$ I think that the notion of pseudo-deterministic algorithm really makes sense only for multi-valued function, otherwise it matches the notion of (standard) randomized algorithm. I took the recent algorithm as an example where the notion fully makes sense in my opinion. $\endgroup$
    – Bruno
    Jul 19, 2023 at 12:04
  • $\begingroup$ Well, usually different runs of a randomized algorithm compute different outputs. Surprisingly, randomization may sometimes help even with computing things that do not depend on the random bits, and this is what a pseudodeterministic algorithm means. This is equally nontrivial when the search problem formally has other solutions, or when it does not. $\endgroup$ Jul 19, 2023 at 12:31
  • $\begingroup$ Though I admit that all randomized decision algorithms are pseudodeterministic in this way, and these are indeed not good examples. $\endgroup$ Jul 19, 2023 at 12:41
1
$\begingroup$

Here is a bit artificial example, not sure whether you'll like it:
Given $m=pq$, where $p$ and $q$ are large primes, and a primitive root $g$ of $\mathbb Z_m^*$, compute $1/g$ or factorize $m$.
Pseudodeterministic algorithm for the problem:
Pick a random $x\in \mathbb Z_m$.
Test whether $x$ and $m$ are relative primes.
If yes, compute $xg, xg^2,\dots$ until we get $1$.
Unless we stumble upon an $x$ that is not relative prime to $m$, this gives the canonical solution $1/g$.
Note that picking a random $x$, instead of starting from $g$, improves the expected running time of the algorithm by a factor of two.

$\endgroup$
2
  • $\begingroup$ What do you mean by a “primitive root of $\mathbb Z_m^*$”? Under the stated assumptions, $\mathbb Z_m^*$ is not cyclic (unless $p=q$). Anyway, $1/g$ modulo $m$ is easy to compute deterministically. $\endgroup$ Jul 19, 2023 at 9:51
  • $\begingroup$ I know that $1/g$ is easy to compute, but I don't think this should be an issue for a toy example. Not being cyclic is a bigger problem... $\endgroup$
    – domotorp
    Jul 19, 2023 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.