Class Description

MA': Sparse MA

The subclass of MA such that for each input size n, there is a sparse set S_n that Merlin's proof string always belongs to (no matter what the input is).

Defined in [KST93], where it is also observed that if graph isomorphism is in P/poly, then the complement of graph isomorphism is in MA'.

Linked From

No class.