# 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.

-

 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. – Tom 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. – Tom 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. – Tom Oct 26 '11 at 6:34