5
$\begingroup$

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.

$\endgroup$
17
  • 2
    $\begingroup$ In other words, $\mathrm{MA}^*=\exists\cdot\mathrm{BPP}$. $\endgroup$ Feb 7, 2021 at 11:32
  • 2
    $\begingroup$ By the way, since BPP is closed under Turing reductions, you also have $\mathrm{MA^*=NP^{BPP}}$. $\endgroup$ Feb 7, 2021 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$ Feb 7, 2021 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$ Feb 7, 2021 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$ Feb 7, 2021 at 19:03

1 Answer 1

4
$\begingroup$

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

$\endgroup$

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.