6

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.

Turbo
  • 12,812
  • 1
  • 19
  • 68
J.Ask
  • 101
  • 4
  • 2
    In other words, $\mathrm{MA}^*=\exists\cdot\mathrm{BPP}$. – Emil Jeřábek Feb 07 '21 at 11:32
  • 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 Feb 07 '21 at 11:51
  • 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 Feb 07 '21 at 12:02
  • 2
    By the way, since BPP is closed under Turing reductions, you also have $\mathrm{MA^*=NP^{BPP}}$. – Emil Jeřábek Feb 07 '21 at 12:03
  • 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 Feb 07 '21 at 12:14
  • 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}^$. – Emil Jeřábek Feb 07 '21 at 12:39
  • 3
    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}$. – Lieuwe Vinkhuijzen Feb 07 '21 at 14:22
  • @LieuweVinkhuijzen WHy is it in NP^RP? – Turbo Feb 07 '21 at 17:01
  • 1
    @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 Feb 07 '21 at 19:03
  • Ok I didn't realize rp was not low for np. – Turbo Feb 08 '21 at 02:55
  • 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 Feb 08 '21 at 09:23
  • @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. – Peter Shor Feb 08 '21 at 12:26
  • @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 Feb 08 '21 at 14:11
  • Based on the responses I am getting, I’m beginning to suspect that my comment 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 Feb 08 '21 at 14:18
  • 1
    @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 Feb 08 '21 at 14:22
  • @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 Feb 08 '21 at 14:59
  • 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 Feb 10 '21 at 22:07

1 Answers1

5

$\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}}$).

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90