文章基本信息

标题：Complete Problems for Multi-Pseudodeterministic Computations
本地全文：下载
作者：Peter Dixon ; A. Pavan ; N. V. Vinodchandran 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：185
页码：66:1-66:16
DOI：10.4230/LIPIcs.ITCS.2021.66
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Pseudodeterminism; Completeness; Collision Probability; Circuit Acceptance; Entropy Approximation