Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Arora and Barak show that $\mathsf{AM}$ can be expressed as $\mathsf{BP}\cdot \mathsf{NP}$ i.e the set of languages that have randomized reductions to 3SAT. $\mathsf{MA}$ is also a natural randomized generalization of $\mathsf{NP}$ in that you replace the deterministic verifier by a randomized one.
Is there a sense in which one of these is a closer fit in the "P is to BPP as NP is to ?" relation ?
This is of course a very subjective matter, but here is something that might be interpreted as saying that $\mathbf{MA}$ is a closer fit: The same assumptions that imply that $\mathbf{P} = \mathbf{BPP}$ also imply that $\mathbf{NP} = \mathbf{MA}$, but those assumptions are not known to imply $\mathbf{NP} = \mathbf{AM}$. In addition, the assumption that $\mathrm{promise}\mathbf{P} = \mathrm{promise}\mathbf{BPP}$ implies that $\mathrm{promise}\mathbf{NP} = \mathrm{promise}\mathbf{MA}$, but is not known to imply $\mathrm{promise}\mathbf{NP} = \mathrm{promise}\mathbf{AM}$.
However, there is an alternative view saying that $\mathbf{MA}$ is the non-deterministic variant of $\mathbf{BPP}$ while $\mathbf{AM}$ is the probabilistic variant of $\mathbf{NP}$. The foregoing facts can also be interpreted as evidence for this view.
Here is a point for AM: For a complexity class C, almost-C is define to be the set of languages that are in C relative to almost every oracle (almost = Probability 1). Then almost-P=BPP and almost-NP=AM.
To throw in another view, IP is the generalization if you think about NP as what you can prove to a polynomial-time skeptic.
