Complete Problems for Multi-Pseudodeterministic Computations
Dixon, Peter, A. Pavan, N. V. Vinodchandran · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2021
We exhibit several computational problems that are complete for multi-pseudodeterministic computations in the following sense: (1) these problems admit 2-pseudodeterministic algorithms (2) if there exists a pseudodeterministic algorithm for any of these problems, then any multi-valued function that admits a k-pseudodeterministic algorithm for a constant k, also admits a pseudodeterministic algorithm. We also show that these computational problems are complete for Search-BPP: a pseudodeterministic algorithm for any of these problems implies a pseudodeterministic algorithm for all problems in Search-BPP.