Computational Complexity

Monday, December 09, 2002

 
Complexity Class of the Week: MA

Posted by Lance

Previous CCW

MA gets its name from the Arthur-Merlin games developed by Babai. MA is an interactive proof system where the all-powerful Merlin sends a message that is verified by a probabilistic Arthur. Here is a formal definition.

A language L is in MA if there is a probabilistic polynomial-time machine M and a polynomial p such that for all strings x,

1. If x is in L then there is a w, |w|=p(|x|) and M(x,w) accepts with probability at least 2/3.
2. If x is not in L then for all w, |w|=p(|x|), M(x,w) accepts with probability at most 1/3.

As with many other interactive proof classes, the 1/3 can be replaced with a value exponentially small in |x| and the 2/3 can be replaced by 1.

The w is a proof that Merlin can write down and Arthur can verify years later without further interaction from Merlin. Sometimes MA is called the class of languages with publishable proofs.

Despite the naturalness of the class, there are no known natural problems in MA not known to be in NP∪BPP.

MA contains NP and BPP and also NP^BPP. MA is contained in its cousin class AM and thus BPP^NP. MA is also contained in many of the same classes BPP is contained in, including S₂, ZPP^NP, Σ₂∩Π₂ and PP. There are oracles where AM is not contained in these classes. Also none of these containments are tight in all relativized worlds.

If L is checkable and has polynomial-size circuit then L is in MA. I will leave the definition of checkable to another post but this implies

If EXP is in P/poly then EXP is in MA. We can replace EXP in the above statement with PSPACE or PP. Using the above statement one can show that MA_EXP does not have polynomial-size circuits. MA_EXP is like MA with polynomials replaced with exponentials.

A strong pseudorandom generator that derandomizes probabilistic circuits will also derandomize MA to NP. Using the result of Impagliazzo-Wigderson we get: If E require 2^{ε n} size circuits for some ε>0 then MA = NP.

The quantum version of MA, QMA has gotten some recent attention. Here Merlin sends entangled quantum bits and Arthur does quantum transformations and measurements. We will discuss QMA another day when it has its turn as complexity class of the week.

10:56 AM # 0 comments

Comment Feeds: This Post All