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.

  • $\begingroup$ @Tom: From your comment, I doubt that you understand the definition of FNP. Please check the definition of FNP. $\endgroup$ – Tsuyoshi Ito Oct 25 '11 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy