Class Description

UAM^cc: Unambiguous Arthur-Merlin Communication Complexity

Similar to AM^cc except that for each yes-input and each outcome of Arthur’s (i.e., Alice's and Bob's) randomness, there must be a unique proof Merlin can send that will be accepted.

Does not contain NP^cc [GPW16a].

Is not contained in SBP^cc [GPW16a], [GLM+15].

Is contained in PostBPP^cc.

Linked From

No class.