<p>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}$.</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-11T02:16:20.703Z
2012-04-11T02:16:20.703Z
Or Meir
<p>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.</p>

CC BY-SA 3.0
2012-04-11T05:27:28.193Z
2012-04-11T05:27:28.193Z
Noam
<p>To throw in another view, IP is the generalization if you think about NP as what you can prove to a polynomial-time skeptic. </p>

CC BY-SA 3.0
2012-04-11T12:53:51.320Z
2012-04-11T12:53:51.320Z
Lance Fortnow
<p>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. </p>

<p>Is there a sense in which one of these is a closer fit in the "P is to BPP as NP is to ?"  relation ? </p>

CC BY-SA 3.0
2012-04-11T12:51:33.897Z
Just to give credit where it's due, Zachos was the first to express AM as BP$\cdot$NP.
Lance Fortnow
CC BY-SA 3.0
2012-04-11T17:54:59.243Z
Yes, I was referring to the textbook without being careful. Thanks !
Suresh Venkat
<cc.complexity-theory><big-picture>
AM/MA and NP in analogy to P and BPP
Suresh Venkat
# AM/MA and NP in analogy to P and BPP

(Asked by: username_0 on 2012-04-10)

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 ?

**Tags:** cc.complexity-theory, big-picture
> **Comments:**
> **username_1**: Just to give credit where it's due, Zachos was the first to express AM as BP$\cdot$NP.  
> **username_0**: Yes, I was referring to the textbook without being careful. Thanks !  

---

## 3 answers

### Answer by username_2 on 2012-04-11. Score: 19

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.


---

### Answer by username_3 on 2012-04-11. Score: 18

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.


---

### Answer by username_1 on 2012-04-11. Score: 11

To throw in another view, IP is the generalization if you think about NP as what you can prove to a polynomial-time skeptic.


---

