Class Description

PSPACEcc: Communication Complexity PSPACE

This class is not defined in terms of space, but rather by analogy with the characterization PSPACE=AP. Specifically, a protocol corresponds to a boolean formula where each leaf represents (the indicator function of) a rectangle; the cost of a protocol is the log of the size of the formula.

Contains PHcc.

Linked From

No class.