4
$\begingroup$

Is there any example of any natural problem which is known to be in MA, but not yet to known to be in NP?

I am aware that Graph Nonisomorphism (GNI) is known to be in AM which is considered a superset of MA. Can we construct a language (which may be non-natural) which is in MA, but not in NP?

$\endgroup$
1
  • $\begingroup$ Since MA is in the polynomial hierarchy, there is no such unconditional result. $\endgroup$ Nov 24, 2017 at 16:06

1 Answer 1

3
$\begingroup$

The same hardness assumption that implies P=BPP also implies NP=MA (at least according to the complexity zoo).

Even if the hardness assumption is wrong, separating NP from MA would be a huge achievement, since it would imply that P is different from NP (as MA is in the polynomial hierarchy).

$\endgroup$
2
  • 1
    $\begingroup$ Yes. separating NP from MA unconditionally would be very hard. (even showing their equality will lead to NEXP $\not\subset$ P/poly, which seems very hard to prove). But my question is a little different: Is something known to be in MA, but not (known) to be in NP (or at least we are unable to prove it is in NP yet)? For example: We can prove GNI is in AM, but it is not known to be in MA (or NP) yet. (Still they are not ruled out). $\endgroup$ Nov 24, 2017 at 16:46
  • 1
    $\begingroup$ For example: A lot of problems are known to be in BPP, but not in P (Polynomial Identity Testing being one example). Similarly, Does the same thing happen in their non-deterministic counterpart as well? $\endgroup$ Nov 24, 2017 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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