Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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
@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

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.