Oded's choices (Nr. 301)

Promise Problems Meet Pseudodeterminism

by Peter Dixon, A. Pavan, and N.V. Vinodchandran

Oded's comments

In my gift to Shafi, I noted a relation between subclasses of the class of search problems that have efficiently recognizable solutions and BPP in its traditional (decision) and promise problem versions. In particular:

A problem in this class can be solved by a polynomial-time pseudodeterministic algorithm if and only if it is reducible in deterministic polynomial-time to a decision problem in BPP [Thm 12].
A problem in this class can be solved by a probabilistic polynomial-time algorithm (with two sided error) if and only if it is reducible in deterministic polynomial-time to a promise problem in BPP [Thm 13].

As I noted elsewhere, I find it interesting that, in this case, the syntactic difference between pure decision and promise problems is translated to a difference between two natural notions of efficient algorithms. The current work makes this point even more explicitly: The former difference is captured by the question of whether a generic approximation problem (i.e., APEP) has a polynomial-time pseudodeterministic algorithm.

The original abstract

The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high probability. Recently, it was shown that such an algorithm would imply that every approximation algorithm can be made pseudodeterministic (Dixon, Pavan, Vinodchandran; (ITCS 2021).

The main conceptual contribution of this work is to establish that the existence of a pseudodeterministic algorithm for APEP is fundamentally connected to the relationship between probabilistic promise classes and the corresponding standard complexity classes. In particular, we show the following equivalence: every promise problem in PromiseBPP has a solution in BPP if and only if APEP has a pseudodeterministic algorithm. Based on this intuition, we show that pseudodeterministic algorithms for APEP can shed light on a few central topics in complexity theory such as circuit lowerbounds, probabilistic hierarchy theorems, and multi-pseudodeterminism.

See ECCC TR21-043

Back to list of Oded's choices.