12
$\begingroup$

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 ?

$\endgroup$
  • 11
    $\begingroup$ Just to give credit where it's due, Zachos was the first to express AM as BP$\cdot$NP. $\endgroup$ – Lance Fortnow Apr 11 '12 at 12:51
  • $\begingroup$ Yes, I was referring to the textbook without being careful. Thanks ! $\endgroup$ – Suresh Venkat Apr 11 '12 at 17:54
17
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.