It is believed that $BPP$ has no complete problems. Even for $BPP^O$ for a suitable oracle $O$ it is believed not to have complete problemaproblems, unless P=BPP. I wonder if the class MA (the randomized version of NP) has complete problems. For example, IP has complete problems (given that it is equal to PSPACE). There is a similar post asking about complexity classes with no complete problems. Here, I'm interested specifically on complete problems for MA. If the answer is positive, can you give some examples? I've tried google and the complexity zoo, but with no success.
|
4 | edited body | ||
|
|
||||
|
|
3 | added 7 characters in body | ||
|
It is believed that $BPP$ has no complete problems. Even for $BPP^O$ for any a suitable oracle $O$ it is believed not to have complete problema, unless P=BPP. I wonder if the class MA (the randomized version of NP) has complete problems. For example, IP has complete problems (given that it is equal to PSPACE). There is a similar post asking about complexity classes with no complete problems. Here, I'm interested specifically on complete problems for MA. If the answer is positive, can you give some examples? I've tried google and the complexity zoo, but with no success. |
||||
|
|
2 | added 44 characters in body | ||
|
It is clear believed that $BPP$ has no complete problems. Even for $BPP^O$ for any oracle $O$ has it is believed not to have complete problemsproblema, unless P=BPP. I wonder if the class MA (the randomized version of NP) has complete problems. For example, IP has complete problems (given that it is equal to PSPACE). There is a similar post asking about complexity classes with no complete problems. Here, I'm interested specifically on complete problems for MA. If the answer is positive, can you give some examples? I've tried google and the complexity zoo, but with no success. |
||||
|
1 |
|
||
