# Merlin-Arthur complexity class for function problems

Quoting wikipedia, the complexity class $MA$ is the set of decision problems that can be decided in polynomial time by an Arthur–Merlin protocol where Merlin's only move precedes any computation by Arthur. In other words, a language $L$ is in $MA$ if there exists a polynomial-time deterministic Turing machine $M$ and polynomials $p$, $q$ such that for every input string $x$ of length $n = |x|$,

• if $x$ is in $L$, then $\exists z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=1)\ge2/3$
• if $x$ is not in $L$, then $\forall z\in\{0,1\}^{q(n)}\,\Pr\nolimits_{y\in\{0,1\}^{p(n)}}(M(x,y,z)=0)\ge2/3$

How does one define MA class for function problems, i.e., problems with range that is not True/False. e.g, finding the factors of a number.

-

There are several reasonable ways to define the function analog of the class MA, and the right definition to choose depends on what you want to use the defined class for.

If we consider NP instead of MA, there are at least two function analogs: FNP and NPMV. (If you want to, you can also count the variations of NPMV such as NPSV, NPSVt, and NPMVt). The MA version of each of these can be naturally defined.

-
thanks for the comment. Perhaps I should have been more specific: I'm looking for a standard extension for MA, that is, like in FNP. But there are some subtle points in the definition. –  User1234 Oct 25 '11 at 16:45
The completeness is very simple to define: If there exists a witness $w$ such that $Pr[\mathcal{A}(x,w)=f(x)]>1-\epsilon$. But the soundness is a bit more subtle, I think. –  User1234 Oct 25 '11 at 16:48
@Tom: From your comment, I doubt that you understand the definition of FNP. Please check the definition of FNP. –  Tsuyoshi Ito Oct 25 '11 at 17:06
Oh, you're right, I've confused FNP with something else. So allow me to correct myself - I'm looking for extending MA for problems with a multi-valued range, in such a way that ensures that there exists a proof for the correct value that can be verified w.h.p., and no such proof exists for a wrong value. –  User1234 Oct 26 '11 at 6:34