Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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