patternMinor
Complexity class NP and MA
Viewed 0 times
andclasscomplexity
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#84418, answer score: 3
Revisions (0)
No revisions yet.