## 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.