Take the 2-minute tour ×
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.

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|improve this question

1 Answer 1

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

Your Answer

 
discard

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.