A previous version of this question asked about a complexity class I called $MA^*$, which has been recognized by users to be $\exists BPP$.

The difference between $MA$ and $\exists BPP$ is that in the latter class the probabilistic verifier decides a BPP language; while the probabilistic verifier in $MA$, when $x\in L$, is required to accept with bounded error only for one certificate and can answer just randomly for all the others, thus violating the BPP promise.

What is the natural reason to allow this "strange" power to the class? E.g. an $MA$ language which is not (trivially) in $\exists BPP$ would answer the question. More generally, in which contexts the class $MA$ comes up naturally but $\exists BPP$ wouldn't (trivially) work?

P.S. For now, I'm answering me as follows. A set $C$ of certificates $x,c$ for $x \in L$ makes sense only in reference to a verification procedure for $(x,c)$. If the verifier is probabilistic, and we want bounded error, there could be some $x,c$ that aren't decided. For $x \notin L$, it remains defined that $(x,c) \notin C$, or soundness is compromised. But what should define $(x,c) \in C$ for $x \in L$, if not the verification procedure itself? So in this sense $MA$ is more natural than $\exists BPP$, because $MA$ doesn't assume $C$ before the verification procedure.

  • 2
    $\begingroup$ In other words, $\mathrm{MA}^*=\exists\cdot\mathrm{BPP}$. $\endgroup$ – Emil Jeřábek Feb 7 at 11:32
  • 2
    $\begingroup$ By the way, since BPP is closed under Turing reductions, you also have $\mathrm{MA^*=NP^{BPP}}$. $\endgroup$ – Emil Jeřábek Feb 7 at 12:03
  • 1
    $\begingroup$ I can’t recall any natural problem in either MA or $\mathrm{MA}^*$ that’s not already in NP or BPP. However, MA comes up naturally in various structural results in complexity theory such as $\mathrm{EXP\subseteq P/poly\implies EXP=MA}$, and these are not known to hold with $\mathrm{MA}^*$. $\endgroup$ – Emil Jeřábek Feb 7 at 12:39
  • 3
    $\begingroup$ This class is in the zoo, here. It notes, as you may already have, that $\text{NP}\subseteq \text{MA}^\ast=\text{NP}^{\text{BPP}}\subseteq \text{MA}$. $\endgroup$ – Lieuwe Vinkhuijzen Feb 7 at 14:22
  • 1
    $\begingroup$ @1.. Correction: the minimization of d-DNNF Boolean circuits is in $NP^{RP}$. A d-DNNF circuit has enough structure to allow a $\text{coRP}$ identity test. Therefore, the NP Machine can supply the smaller circuit, and then the RP oracle can verify that the circuit supplied behaves identically to the given circuit. This problem is therefore in $NP^{RP}$. (I have deleted the previous comment). $\endgroup$ – Lieuwe Vinkhuijzen Feb 7 at 19:03

$\def\mr{\mathrm}$First, standard derandomization assumptions (the existence of a language in $\mr E$ that requires circuit size $2^{\Omega(n)}$) imply $\mr{promise\text-BPP=promise\text-P}$, hence $$\mr{MA=\exists BPP=NP},$$ thus any difference between the two classes is likely just an artifact of our incomplete knowledge.

Having said that, there are several results in complexity theory involving $\mr{MA}$ that are not known to hold for $\exists\mr{BPP}$. In particular, there is a group of results of the form $$\begin{align*} \mr{PP\subseteq P/poly}&\implies\mr{PP=MA},\\ \mr{PSPACE\subseteq P/poly}&\implies\mr{PSPACE=MA},\\ \mr{EXP\subseteq P/poly}&\implies\mr{EXP=MA},\\ \mr{NEXP\subseteq P/poly}&\implies\mr{NEXP=MA}. \end{align*}$$ (The first three results are due to Babai, Fortnow & Lund, the last one is due to Impagliazzo, Kabanets & Wigderson.)

If you allow me larger time bounds, an often quoted related result is that $$\mr{MA\text-EXP\nsubseteq P/poly}$$ (here, $\mr{MA\text-EXP=MA\text-TIME}(2^{n^{O(1)}})$ is the exponential analogue of $\mr{MA}$). In fact, this result can be improved, nevertheless it is not known to be true for $\mr{NEXP^{BPP}}$ (which is the exponential analogue of $\exists\mr{BPP}=\mr{NP^{BPP}}$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.