2026-07-25T21:16:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13605 2024-03-06T10:52:25Z ddc:004 open_access

Complete Problems for Multi-Pseudodeterministic Computations Dixon, Peter Pavan, A. Vinodchandran, N. V. Pseudodeterminism Completeness Collision Probability Circuit Acceptance Entropy Approximation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peter Dixon and A. Pavan and N. V. Vinodchandran 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.66 urn:nbn:de:0030-drops-136050 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.66 eng https://creativecommons.org/licenses/by/3.0/legalcode