Class Description

UAMcc: Unambiguous Arthur-Merlin Communication Complexity

Similar to AMcc 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 NPcc [GPW16a].

Is not contained in SBPcc [GPW16a], [GLM+15].

Is contained in PostBPPcc.

Linked From

No class.