Co-Merlin-Arthur

The complement class of MA: a problem is in coMA if its complement is in MA — standard.

See the complexity zoo entry here.

Known relationships

• $\mathbf{coMA}\subseteq \mathbf{coAM}$, by taking complements in $\mathbf{MA}\subseteq \mathbf{AM}$ — BM88.
• $\mathbf{coNP}\subseteq \mathbf{coMA}$ and $\mathbf{BPP}\subseteq \mathbf{coMA}$, by taking complements in $\mathbf{NP}\subseteq \mathbf{MA}$ and $\mathbf{BPP}\subseteq \mathbf{MA}$ — standard.
• $\mathbf{NP}\subseteq \mathbf{coMA}$ would give $\mathbf{coNP}\subseteq \mathbf{MA}\subseteq \mathbf{AM}$ and collapse the polynomial hierarchy to its second level — BHZ87, BM88.

Participates in

Produces Co-Merlin-Arthur

• Four-message black-box ZK proofs ⊆ coMA