<p><span class="math-container">$\def\mr{\mathrm}$</span>First, standard derandomization assumptions (the existence of a language in <span class="math-container">$\mr E$</span> that requires circuit size <span class="math-container">$2^{\Omega(n)}$</span>) imply <span class="math-container">$\mr{promise\text-BPP=promise\text-P}$</span>, hence
<span class="math-container">$$\mr{MA=\exists BPP=NP},$$</span>
thus any difference between the two classes is likely just an artifact of our incomplete knowledge.</p>
<p>Having said that, there are several results in complexity theory involving <span class="math-container">$\mr{MA}$</span> that are not known to hold for <span class="math-container">$\exists\mr{BPP}$</span>. In particular, there is a group of results of the form
<span class="math-container">$$\begin{align*}
\mr{PP\subseteq P/poly}&amp;\implies\mr{PP=MA},\\
\mr{PSPACE\subseteq P/poly}&amp;\implies\mr{PSPACE=MA},\\
\mr{EXP\subseteq P/poly}&amp;\implies\mr{EXP=MA},\\
\mr{NEXP\subseteq P/poly}&amp;\implies\mr{NEXP=MA}.
\end{align*}$$</span>
(The first three results are due to <a href="https://doi.org/10.1007/BF01200056" rel="noreferrer">Babai, Fortnow &amp; Lund</a>, the last one is due to <a href="https://doi.org/10.1016/S0022-0000(02)00024-7" rel="noreferrer">Impagliazzo, Kabanets &amp; Wigderson</a>.)</p>
<p>If you allow me larger time bounds, an often quoted related result is that
<span class="math-container">$$\mr{MA\text-EXP\nsubseteq P/poly}$$</span>
(here, <span class="math-container">$\mr{MA\text-EXP=MA\text-TIME}(2^{n^{O(1)}})$</span> is the exponential analogue of <span class="math-container">$\mr{MA}$</span>). In fact, this result can be <a href="https://cstheory.stackexchange.com/a/40768">improved</a>, nevertheless it is not known to be true for <span class="math-container">$\mr{NEXP^{BPP}}$</span> (which is the exponential analogue of <span class="math-container">$\exists\mr{BPP}=\mr{NP^{BPP}}$</span>).</p>

CC BY-SA 4.0
2021-02-08T09:19:10.333Z
2021-02-08T09:19:10.333Z
Emil Jeřábek
<p>NP can be defined as the class of languages which admit sets of certificates which are in P. The definition could be as follows.</p>
<p>A language <span class="math-container">$L$</span> is in <span class="math-container">$NP$</span> iff there is a set <span class="math-container">$C=\left\{ x,c\right\}$</span> and a polynomial <span class="math-container">$p$</span> such that:</p>
<ul>
<li><span class="math-container">$x\in L\rightarrow \exists c ((x,c)\in C)$</span></li>
<li><span class="math-container">$x\notin L\rightarrow \forall c ((x,c)\notin C)$</span></li>
<li><span class="math-container">$(x,c)\in C\rightarrow |c|\leq p(|x|)$</span></li>
<li><span class="math-container">$C\in P$</span></li>
</ul>
<p>This doesn't work for MA, because the probabilistic verifier there is not required to decide any BPP language: when <span class="math-container">$x\notin L$</span> it always refuse with bounded error, but when <span class="math-container">$x\in L$</span> the verifier is required to accept with bounded error only for one certificate, for all the others it could answer just randomly and thus violate the BPP promise.</p>
<p>What about the following class then?</p>
<p>A language <span class="math-container">$L$</span> is in <span class="math-container">$MA^*$</span> iff there is a set <span class="math-container">$C=\left\{ x,c\right\}$</span> and a polynomial <span class="math-container">$p$</span> such that:</p>
<ul>
<li><span class="math-container">$x\in L\rightarrow \exists c ((x,c)\in C)$</span></li>
<li><span class="math-container">$x\notin L\rightarrow \forall c ((x,c)\notin C)$</span></li>
<li><span class="math-container">$(x,c)\in C\rightarrow |c|\leq p(|x|)$</span></li>
<li><span class="math-container">$C\in BPP$</span></li>
</ul>
<p>It is clearly <span class="math-container">$MA^* \subseteq MA$</span> but not the opposite (at least not trivially). My questions are  as follows. Is <span class="math-container">$MA^*$</span> somewhat known and studied? And why is <span class="math-container">$MA$</span> more relevant?</p>
<p><strong>UPDATES</strong></p>
<p>A previous version of this question presented above asked about a complexity class I called <span class="math-container">$MA^*$</span>, which has been recognized by users to be <span class="math-container">$\exists BPP$</span>.</p>
<p>The difference between <span class="math-container">$MA$</span> and <span class="math-container">$\exists BPP$</span> is that in the latter class the probabilistic verifier decides a BPP language; while the probabilistic verifier in <span class="math-container">$MA$</span>,  when <span class="math-container">$x\in L$</span>, 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.</p>
<p>What is the natural reason to allow this &quot;strange&quot; power to the class? E.g. an <span class="math-container">$MA$</span> language which is not (trivially) in <span class="math-container">$\exists BPP$</span> would answer the question. More generally, in which contexts the class <span class="math-container">$MA$</span> comes up naturally but <span class="math-container">$\exists BPP$</span> wouldn't (trivially) work?</p>
<p>P.S. For now, I'm answering me as follows. A set <span class="math-container">$C$</span> of certificates <span class="math-container">$x,c$</span> for <span class="math-container">$x \in L$</span> makes sense only in reference to a verification procedure for <span class="math-container">$(x,c)$</span>. If the verifier is probabilistic, and we want bounded error, there could be some <span class="math-container">$x,c$</span> that aren't decided. For <span class="math-container">$x \notin L$</span>, it remains defined that <span class="math-container">$(x,c) \notin C$</span>, or soundness is compromised. But what should define <span class="math-container">$(x,c) \in C$</span> for <span class="math-container">$x \in L$</span>, if not the verification procedure itself? So in this sense <span class="math-container">$MA$</span> is more natural than <span class="math-container">$\exists BPP$</span>, because <span class="math-container">$MA$</span> doesn't assume <span class="math-container">$C$</span> before the verification procedure.</p>

CC BY-SA 4.0
2021-02-07T11:32:52.207Z
In other words, $\mathrm{MA}^*=\exists\cdot\mathrm{BPP}$.
Emil Jeřábek
CC BY-SA 4.0
2021-02-07T11:51:15.250Z
I think I have encountered many times this dot product notation for complexity classes, but I am not sure of its meaning. Could you link me to a definition?
J.Ask
CC BY-SA 4.0
2021-02-07T12:02:16.920Z
The dot notation does not mean much by itself, it just denotes an application of the $\exists$ *class operator* to BPP. You can actually write it as just $\exists\mathrm{BPP}$. See e.g. https://cstheory.stackexchange.com/questions/21602/a-good-reference-for-complexity-class-operators.
Emil Jeřábek
CC BY-SA 4.0
2021-02-07T12:03:31.813Z
By the way, since BPP is closed under Turing reductions, you also have $\mathrm{MA^*=NP^{BPP}}$.
Emil Jeřábek
CC BY-SA 4.0
2021-02-07T12:14:33.307Z
I cannot upvote yet so: thanks! A last question: do you have in mind a "natural" MA language which is not (trivially) in MA*?
J.Ask
CC BY-SA 4.0
2021-02-07T12:39:38.493Z
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}^*$.
Emil Jeřábek
CC BY-SA 4.0
2021-02-07T14:22:29.067Z
This class is in the zoo, [here](https://complexityzoo.net/Complexity_Zoo:E#existsbpp). It notes, as you may already have, that $\text{NP}\subseteq \text{MA}^\ast=\text{NP}^{\text{BPP}}\subseteq \text{MA}$.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2021-02-07T17:01:47.053Z
@LieuweVinkhuijzen WHy is it in NP^RP?
Turbo
CC BY-SA 4.0
2021-02-07T19:03:03.293Z
@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).
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2021-02-08T02:55:31.983Z
Ok I didn't realize rp was not low for np.
Turbo
CC BY-SA 4.0
2021-02-08T09:23:44.853Z
Since my comment above now fits the revised question (“in which contexts the class MA comes up naturally but ∃BPP wouldn't (trivially) work”), I expanded it to an answer.
Emil Jeřábek
CC BY-SA 4.0
2021-02-08T12:26:24.153Z
@EmilJeřábek: The promise problem stoquastic 6-SAT (essentially, estimating the ground state energy of a frustration-free stoquastic Hamiltonian where each term is 6-local) is MA-complete. [See Bravyi, Bessen and Terhal](https://arxiv.org/abs/quant-ph/0611021v1).
Peter Shor 
CC BY-SA 4.0
2021-02-08T14:11:13.590Z
@PeterShor Since this is a promise problem, you mean that it is **promiseMA**-complete, right? MA is a semantic class and, similar to BPP, is not known to have complete problems. But anyway, if you have an interesting answer to the OP’s question, please post it as an answer, not as a comment directed to me.
Emil Jeřábek
CC BY-SA 4.0
2021-02-08T14:18:14.453Z
Based on the responses I am getting, I’m beginning to suspect that my [comment](https://cstheory.stackexchange.com/questions/48338/where-is-ma-more-relevant-than-exists-bpp#comment107439_48338) above is prone to misunderstanding. It only means what it literally says: that I couldn’t think of any interesting problems in MA off the top of my head. It was not at all my intention to suggest that no such problems exist.
Emil Jeřábek
CC BY-SA 4.0
2021-02-08T14:22:19.617Z
@EmilJeřábek: Yes, I meant promise-MA-complete. But by the very nature of MA, it seems that you can't have MA-complete problems, just promise problems that are promise-MA-complete.  And before I post it as an answer, I want to check that there aren't any promiseMA*-complete problems.
Peter Shor 
CC BY-SA 4.0
2021-02-08T14:59:01.597Z
@PeterShor The whole difference between MA and MA* is predicated on the difference between promiseBPP and BPP. How do you define promiseMA* so that it is different from promiseMA?
Emil Jeřábek
CC BY-SA 4.0
2021-02-10T22:07:49.803Z
PromiseMA* would be like promiseMA with the difference that we can always answer with bounded error for certificates of yes instances.  This could work for stoqsat, as certificates are discrete strings. Wouldn't that mean MA=MA*?
J.Ask
<complexity-classes><promise-problems><probabilistic-complexity>
Where is $MA$ more relevant than $\exists BPP$?
J.Ask
# Where is $MA$ more relevant than $\exists BPP$?

(Asked by: username_0 on 2021-02-07)

NP can be defined as the class of languages which admit sets of certificates which are in P. The definition could be as follows.

A language $L$ is in $NP$ iff there is a set $C=\left\{ x,c\right\}$ and a polynomial $p$ such that:

* $x\in L\rightarrow \exists c ((x,c)\in C)$
* $x\notin L\rightarrow \forall c ((x,c)\notin C)$
* $(x,c)\in C\rightarrow |c|\leq p(|x|)$
* $C\in P$

This doesn't work for MA, because the probabilistic verifier there is not required to decide any BPP language: when $x\notin L$ it always refuse with bounded error, but when $x\in L$ the verifier is required to accept with bounded error only for one certificate, for all the others it could answer just randomly and thus violate the BPP promise.

What about the following class then?

A language $L$ is in $MA^\*$ iff there is a set $C=\left\{ x,c\right\}$ and a polynomial $p$ such that:

* $x\in L\rightarrow \exists c ((x,c)\in C)$
* $x\notin L\rightarrow \forall c ((x,c)\notin C)$
* $(x,c)\in C\rightarrow |c|\leq p(|x|)$
* $C\in BPP$

It is clearly $MA^\* \subseteq MA$ but not the opposite (at least not trivially). My questions are as follows. Is $MA^\*$ somewhat known and studied? And why is $MA$ more relevant?

**UPDATES**

A previous version of this question presented above 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.

**Tags:** complexity-classes, promise-problems, probabilistic-complexity
> **Comments:**
> **username_1**: In other words, $\mathrm{MA}^*=\exists\cdot\mathrm{BPP}$.  
> **username_0**: I think I have encountered many times this dot product notation for complexity classes, but I am not sure of its meaning. Could you link me to a definition?  
> **username_1**: The dot notation does not mean much by itself, it just denotes an application of the $\exists$ *class operator* to BPP. You can actually write it as just $\exists\mathrm{BPP}$. See e.g. https://cstheory.stackexchange.com/questions/21602/a-good-reference-for-complexity-class-operators.  
> **username_1**: By the way, since BPP is closed under Turing reductions, you also have $\mathrm{MA^*=NP^{BPP}}$.  
> **username_0**: I cannot upvote yet so: thanks! A last question: do you have in mind a "natural" MA language which is not (trivially) in MA*?  
> **username_1**: 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}^*$.  
> **username_2**: This class is in the zoo, [here](https://complexityzoo.net/Complexity_Zoo:E#existsbpp). It notes, as you may already have, that $\text{NP}\subseteq \text{MA}^\ast=\text{NP}^{\text{BPP}}\subseteq \text{MA}$.  
> **username_3**: @LieuweVinkhuijzen WHy is it in NP^RP?  
> **username_2**: @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).  
> **username_3**: Ok I didn't realize rp was not low for np.  
> **username_1**: Since my comment above now fits the revised question (“in which contexts the class MA comes up naturally but ∃BPP wouldn't (trivially) work”), I expanded it to an answer.  
> **username_4**: @EmilJeřábek: The promise problem stoquastic 6-SAT (essentially, estimating the ground state energy of a frustration-free stoquastic Hamiltonian where each term is 6-local) is MA-complete. [See Bravyi, Bessen and Terhal](https://arxiv.org/abs/quant-ph/0611021v1).  
> **username_1**: @PeterShor Since this is a promise problem, you mean that it is **promiseMA**-complete, right? MA is a semantic class and, similar to BPP, is not known to have complete problems. But anyway, if you have an interesting answer to the OP’s question, please post it as an answer, not as a comment directed to me.  
> **username_1**: Based on the responses I am getting, I’m beginning to suspect that my [comment](https://cstheory.stackexchange.com/questions/48338/where-is-ma-more-relevant-than-exists-bpp#comment107439_48338) above is prone to misunderstanding. It only means what it literally says: that I couldn’t think of any interesting problems in MA off the top of my head. It was not at all my intention to suggest that no such problems exist.  
> **username_4**: @EmilJeřábek: Yes, I meant promise-MA-complete. But by the very nature of MA, it seems that you can't have MA-complete problems, just promise problems that are promise-MA-complete.  And before I post it as an answer, I want to check that there aren't any promiseMA*-complete problems.  
> **username_1**: @PeterShor The whole difference between MA and MA* is predicated on the difference between promiseBPP and BPP. How do you define promiseMA* so that it is different from promiseMA?  
> **username_0**: PromiseMA* would be like promiseMA with the difference that we can always answer with bounded error for certificates of yes instances.  This could work for stoqsat, as certificates are discrete strings. Wouldn't that mean MA=MA*?  

---

## 1 answers

### Answer by username_1 on 2021-02-08. Score: 6 | Accepted answer

$\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](https://doi.org/10.1007/BF01200056), the last one is due to [Impagliazzo, Kabanets & Wigderson](https://doi.org/10.1016/S0022-0000(02)00024-7).)

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](https://cstheory.stackexchange.com/a/40768), nevertheless it is not known to be true for $\mr{NEXP^{BPP}}$ (which is the exponential analogue of $\exists\mr{BPP}=\mr{NP^{BPP}}$).


---

