9
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 5
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented Jul 2, 2014 at 14:59
  • $\begingroup$ 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}$)! $\endgroup$
    – Bruno
    Commented Jul 2, 2014 at 15:02
  • 2
    $\begingroup$ It's hard finding natural problems in MA. Here 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. $\endgroup$
    – Peter Shor
    Commented Jul 2, 2014 at 15:08
  • $\begingroup$ 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...) $\endgroup$
    – Joshua Grochow
    Commented Jul 2, 2014 at 16:01
  • 2
    $\begingroup$ @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). $\endgroup$
    – Peter Shor
    Commented Jul 2, 2014 at 19:58

1 Answer 1

Reset to default
8
$\begingroup$

[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, but for the purposes of this answer similar ideas go back to an earlier paper of Pitassi's as well as her 1998 ICM talk, and to the so-called Nullstellensatz and Polynomial Calculus proof systems.)

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Bruno
    Commented Jul 3, 2014 at 11:45
  • 1
    $\begingroup$ @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). $\endgroup$
    – Joshua Grochow
    Commented Jul 3, 2014 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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