<p>[I'm posting this as an answer despite being in <span class="math-container">$\mathsf{PromiseMA}$</span> because a) it exhibits a different kind of <span class="math-container">$\mathsf{MA}$</span>-style algorithm, and b) @PeterShor asked  and it was too long for a comment.]</p>
<p>Over any finite field <span class="math-container">$\mathbb{F}$</span>, the following problem is in <span class="math-container">$\mathsf{PromiseMA}$</span>:</p>
<blockquote>
<p><strong>Input</strong>: A set of <span class="math-container">$\mathbb{F}$</span>-polynomials <span class="math-container">$F_1(\vec{x}), \dotsc, F_m(\vec{x})$</span></p>
<p><strong>Decide</strong>: Is there no solution to <span class="math-container">$F_1(\vec{x}) = \dotsb = F_m(\vec{x}) = 0$</span> over the algebraic closure <span class="math-container">$\overline{\mathbb{F}}$</span></p>
<p><strong>Promise</strong>: Either there is a solution over <span class="math-container">$\overline{\mathbb{F}}$</span>, or there is a <em>poly-size</em> <span class="math-container">$\mathbb{F}$</span>-algebraic circuit <span class="math-container">$C(\vec{x}, y_1, \dotsc, y_m)$</span> such that <span class="math-container">$C(\vec{x}, \vec{0}) = 0$</span> and <span class="math-container">$C(\vec{x}, \vec{F}(\vec{x})) = 1$</span> (identically as polynomials)</p>
</blockquote>
<p>The <span class="math-container">$\mathsf{MA}$</span>-style algorithm guesses the circuit <span class="math-container">$C$</span>, and then verifies the two conditions using polynomial identity testing, which is in <span class="math-container">$\mathsf{coRP}$</span> by Schwarz-Zippell-DeMillo-Lipton.</p>
<p>Note that, without the restriction of poly-size, Hilbert's Nullstellensatz guarantees that there is no solution if and only if there is <em>some</em> circuit <span class="math-container">$C$</span> satisfying the above two conditions. (On the other hand, assuming <span class="math-container">$\mathsf{NP} \not\subseteq \mathsf{coMA}$</span>, there are systems of equations coming from algebrizations of 3SAT for which the above poly-size promise is violated.)</p>
<p>(This is the basis of an algebraic proof system from recent <a href="http://eccc.hpi-web.de/report/2014/052/" rel="noreferrer">joint work with Toniann Pitassi</a>, but for the purposes of this answer similar ideas go back to an <a href="http://www.cs.toronto.edu/~toni/Papers/pitassi-algebraic.ps" rel="noreferrer">earlier paper of Pitassi's</a> as well as her <a href="http://www.mathunion.org/ICM/ICM1998.3/Main/14/Pitassi.MAN.ocr.pdf" rel="noreferrer">1998 ICM talk</a>, and to the so-called <a href="http://dx.doi.org/10.1112/plms/s3-73.1.1" rel="noreferrer">Nullstellensatz</a> and <a href="http://dx.doi.org/10.1145/237814.237860" rel="noreferrer">Polynomial Calculus</a> proof systems.)</p>

CC BY-SA 3.0
2014-07-03T11:45:55.077Z
I find it intriguing that this result is very close (in spirit) to a result of Koiran showing that deciding whether a bunch of integer polynomials has a common root in $\mathbb C$ is in $\mathsf{AM}$, though with an apparently unrelated proof. (Koiran's result is based on Goldwasser-Sipser's set lower bound protocol.) While trying to find an example of problem in $\mathsf{MA}$, I was playing with similar problems: Basically, I wanted to use DLSZ lemma at some point.
Bruno
CC BY-SA 3.0
2014-07-03T16:56:41.013Z
@Bruno: I found the same thing intriguing :). In fact, we also get a similar result to the above over fields of characteristic zero, but with $\mathsf{PromiseAM}$ instead of $\mathsf{PromiseMA}$, and the proof uses Koiran's result in a black-box way as a subroutine (see Proposition 2.4 in the joint paper with Pitassi).
Joshua Grochow
CC BY-SA 3.0
2014-07-02T20:40:29.410Z
2014-07-02T20:40:29.410Z
2020-06-17T09:38:08.363Z
Joshua Grochow
<p>What are the examples of problems known to be in $\mathsf{AM}$ (resp. $\mathsf{MA}$) which are not known to be in $\mathsf{NP}$ nor in $\mathsf{BPP}$?</p>

<p>For $\mathsf{AM}$, I know the following two examples:</p>

<ul>
<li><strong>Graph non-isomorphism:</strong> Given two labeled graphs $G$ and $H$, are they the same graph up to permutation of the vertices?</li>
<li><strong>Lower bound protocol:</strong> You are given a set $S\subset\{0,1\}^m$ such that you know that either $|S|\le\alpha|U|$ or $|S|\ge 4\alpha|U|$ for some $0\le\alpha\le 1$, and such that $S\in\mathsf{AM}$ (that is, given $y\in U$, checking whether $y\in S$ can be solved in $\mathsf{AM}$), and you have to decide whether $|S\ge 4\alpha|U|$.</li>
</ul>

<p>For $\mathsf{MA}$, I do not know of any example. </p>

<p>My refined question: Do we know other problems in $\mathsf{AM}$ or $\mathsf{MA}$, not known to be in $\mathsf{NP}\cup\mathsf{BPP}$?</p>

<p>I am not interested in problems for which the only proof that they belong to $\mathsf{AM}$ is by using one of these two protocols. </p>

<p><em>Edit:</em> My main motivation is to be able to give examples of $\mathsf{AM}$ or $\mathsf{MA}$ algorithms to explain what these classes are.</p>

CC BY-SA 3.0
2014-07-02T14:59:02.687Z
This is probably not going to help with your motivation (and so I'm not adding it as an answer), but the quantum stoquastic $k$-SAT problem is MA-complete. That is: does a stoquastic Hamiltonian with $k$-local terms have a frustration-free ground state. *Frustration-free* means all terms are in their lowest energy state; *$k$-local* means each term of the Hamiltonian contains only $k$ qubits; *stoquastic* means all off-diagonal entries of the Hamiltonian matrix are non-positive. See [this paper](http://arxiv.org/abs/quant-ph/0606140).
Peter Shor 
CC BY-SA 3.0
2014-07-02T15:02:20.807Z
Thanks Peter! I think this is a perfectly valid answer even though it is maybe not the best example to give as an help for intuition... But I was not aware of *any* problem in $\mathsf{MA}$ (that is not known to be in $\mathsf{NP}$)!
Bruno
CC BY-SA 3.0
2014-07-02T15:08:43.363Z
It's hard finding natural problems in MA. [Here](http://blog.computationalcomplexity.org/2002/12/complexity-class-of-week-ma.html) is a blog entry from 2002 by Lance Fortnow, where he says that no natural problems are known to be in MA that aren't in NP $\cup$ BPP. And that was still the case in 2006, when Bravyi et al. showed that stoquastic $k$-SAT was in it. (And in case you were wondering, it is indeed a natural problem for quantum computation.) I don't believe anything has changed in the last eight years, but I might easily have missed stuff.
Peter Shor 
CC BY-SA 3.0
2014-07-02T16:01:24.780Z
Would you accept answers that are in $\mathsf{PromiseMA}$ or $\mathsf{PromiseAM}$ that are not known to be in $\mathsf{PromiseNP} \cup \mathsf{PromiseBPP}$? My feeling is that often such problems have good examples of $\mathsf{MA}$- or $\mathsf{AM}$-style algorithms, it's just they're only guaranteed to work when the promise holds... (But if this is for a formal course this may not be a good kind of example, as promise examples often serve to confuse first-time learners...)
Joshua Grochow
CC BY-SA 3.0
2014-07-02T19:58:45.330Z
@Joshua: if you have any natural problems in PromiseMA, I would really like to see them. I think the OP would also, since his lower bound protocol problem for AM is actually a promise problem. I should probably also note that the stochastic $k$-SAT problem is also a promise problem (we promise that either there is a frustration-free ground state, or that the ground state has 1/poly($n$) higher energy than a frustration-free ground state would have).
Peter Shor 
CC BY-SA 3.0
2014-07-02T20:39:06.680Z
@Bruno: I'd refer to what you call the "Lower bound protocol" as a "counting protocol" or even a "Sipser-style counting protocol" (since I believe Sipser was the first to show that such counting could be done efficiently).
Joshua Grochow
CC BY-SA 3.0
2014-07-03T11:49:58.297Z
@Joshua: The name "lower bound protocol" is used by Arora & Barak in their book, and they attribute it to Goldwasser and Sipser. I've also seen the name "approximate counting protocol" in the literature.
Bruno
CC BY-SA 3.0
2014-07-03T15:32:15.073Z
@Bruno: Whoops, I meant Goldwasser-Sipser. Interesting that Arora & Barak call it a lower bound protocol. OK.
Joshua Grochow
<cc.complexity-theory><complexity-classes>
Problems in AM or in MA
Bruno
# Problems in AM or in MA

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

What are the examples of problems known to be in $\mathsf{AM}$ (resp. $\mathsf{MA}$) which are not known to be in $\mathsf{NP}$ nor in $\mathsf{BPP}$?

For $\mathsf{AM}$, I know the following two examples:

* **Graph non-isomorphism:** Given two labeled graphs $G$ and $H$, are they the same graph up to permutation of the vertices?
* **Lower bound protocol:** You are given a set $S\subset\{0,1\}^m$ such that you know that either $|S|\le\alpha|U|$ or $|S|\ge 4\alpha|U|$ for some $0\le\alpha\le 1$, and such that $S\in\mathsf{AM}$ (that is, given $y\in U$, checking whether $y\in S$ can be solved in $\mathsf{AM}$), and you have to decide whether $|S\ge 4\alpha|U|$.

For $\mathsf{MA}$, I do not know of any example.

My refined question: Do we know other problems in $\mathsf{AM}$ or $\mathsf{MA}$, not known to be in $\mathsf{NP}\cup\mathsf{BPP}$?

I am not interested in problems for which the only proof that they belong to $\mathsf{AM}$ is by using one of these two protocols.

*Edit:* My main motivation is to be able to give examples of $\mathsf{AM}$ or $\mathsf{MA}$ algorithms to explain what these classes are.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: This is probably not going to help with your motivation (and so I'm not adding it as an answer), but the quantum stoquastic $k$-SAT problem is MA-complete. That is: does a stoquastic Hamiltonian with $k$-local terms have a frustration-free ground state. *Frustration-free* means all terms are in their lowest energy state; *$k$-local* means each term of the Hamiltonian contains only $k$ qubits; *stoquastic* means all off-diagonal entries of the Hamiltonian matrix are non-positive. See [this paper](http://arxiv.org/abs/quant-ph/0606140).  
> **username_0**: Thanks Peter! I think this is a perfectly valid answer even though it is maybe not the best example to give as an help for intuition... But I was not aware of *any* problem in $\mathsf{MA}$ (that is not known to be in $\mathsf{NP}$)!  
> **username_1**: It's hard finding natural problems in MA. [Here](http://blog.computationalcomplexity.org/2002/12/complexity-class-of-week-ma.html) is a blog entry from 2002 by Lance Fortnow, where he says that no natural problems are known to be in MA that aren't in NP $\cup$ BPP. And that was still the case in 2006, when Bravyi et al. showed that stoquastic $k$-SAT was in it. (And in case you were wondering, it is indeed a natural problem for quantum computation.) I don't believe anything has changed in the last eight years, but I might easily have missed stuff.  
> **username_2**: Would you accept answers that are in $\mathsf{PromiseMA}$ or $\mathsf{PromiseAM}$ that are not known to be in $\mathsf{PromiseNP} \cup \mathsf{PromiseBPP}$? My feeling is that often such problems have good examples of $\mathsf{MA}$- or $\mathsf{AM}$-style algorithms, it's just they're only guaranteed to work when the promise holds... (But if this is for a formal course this may not be a good kind of example, as promise examples often serve to confuse first-time learners...)  
> **username_1**: @Joshua: if you have any natural problems in PromiseMA, I would really like to see them. I think the OP would also, since his lower bound protocol problem for AM is actually a promise problem. I should probably also note that the stochastic $k$-SAT problem is also a promise problem (we promise that either there is a frustration-free ground state, or that the ground state has 1/poly($n$) higher energy than a frustration-free ground state would have).  
> **username_2**: @username_0: I'd refer to what you call the "Lower bound protocol" as a "counting protocol" or even a "Sipser-style counting protocol" (since I believe Sipser was the first to show that such counting could be done efficiently).  
> **username_0**: @Joshua: The name "lower bound protocol" is used by Arora & Barak in their book, and they attribute it to Goldwasser and Sipser. I've also seen the name "approximate counting protocol" in the literature.  
> **username_2**: @username_0: Whoops, I meant Goldwasser-Sipser. Interesting that Arora & Barak call it a lower bound protocol. OK.  

---

## 1 answers

### Answer by username_2 on 2014-07-02. Score: 8

[I'm posting this as an answer despite being in $\mathsf{PromiseMA}$ because a) it exhibits a different kind of $\mathsf{MA}$-style algorithm, and b) @PeterShor asked and it was too long for a comment.]

Over any finite field $\mathbb{F}$, the following problem is in $\mathsf{PromiseMA}$:

> **Input**: A set of $\mathbb{F}$-polynomials $F\_1(\vec{x}), \dotsc, F\_m(\vec{x})$
>
> **Decide**: Is there no solution to $F\_1(\vec{x}) = \dotsb = F\_m(\vec{x}) = 0$ over the algebraic closure $\overline{\mathbb{F}}$
>
> **Promise**: Either there is a solution over $\overline{\mathbb{F}}$, or there is a *poly-size* $\mathbb{F}$-algebraic circuit $C(\vec{x}, y\_1, \dotsc, y\_m)$ such that $C(\vec{x}, \vec{0}) = 0$ and $C(\vec{x}, \vec{F}(\vec{x})) = 1$ (identically as polynomials)

The $\mathsf{MA}$-style algorithm guesses the circuit $C$, and then verifies the two conditions using polynomial identity testing, which is in $\mathsf{coRP}$ by Schwarz-Zippell-DeMillo-Lipton.

Note that, without the restriction of poly-size, Hilbert's Nullstellensatz guarantees that there is no solution if and only if there is *some* circuit $C$ satisfying the above two conditions. (On the other hand, assuming $\mathsf{NP} \not\subseteq \mathsf{coMA}$, there are systems of equations coming from algebrizations of 3SAT for which the above poly-size promise is violated.)

(This is the basis of an algebraic proof system from recent [joint work with Toniann Pitassi](http://eccc.hpi-web.de/report/2014/052/), but for the purposes of this answer similar ideas go back to an [earlier paper of Pitassi's](http://www.cs.toronto.edu/~toni/Papers/pitassi-algebraic.ps) as well as her [1998 ICM talk](http://www.mathunion.org/ICM/ICM1998.3/Main/14/Pitassi.MAN.ocr.pdf), and to the so-called [Nullstellensatz](http://dx.doi.org/10.1112/plms/s3-73.1.1) and [Polynomial Calculus](http://dx.doi.org/10.1145/237814.237860) proof systems.)

> **Comments:**
> **username_0**: I find it intriguing that this result is very close (in spirit) to a result of Koiran showing that deciding whether a bunch of integer polynomials has a common root in $\mathbb C$ is in $\mathsf{AM}$, though with an apparently unrelated proof. (Koiran's result is based on Goldwasser-Sipser's set lower bound protocol.) While trying to find an example of problem in $\mathsf{MA}$, I was playing with similar problems: Basically, I wanted to use DLSZ lemma at some point.  
> **username_2**: @username_0: I found the same thing intriguing :). In fact, we also get a similar result to the above over fields of characteristic zero, but with $\mathsf{PromiseAM}$ instead of $\mathsf{PromiseMA}$, and the proof uses Koiran's result in a black-box way as a subroutine (see Proposition 2.4 in the joint paper with Pitassi).  

---

