Results on communication complexity classes

摘要

Deterministic, probabilistic, nondeterministic, and alternating complexity classes defined by polylogarithmic communication are considered. Main results are (1) extending work of Ja′Ja′, Prasanna Kumar, and Simon, we give a simple technique allowing translation of most known separation and containment results for complexity classes of the fixed partition model to the more difficult optimal partition model, where few results were previously known; and (2) demonstration that a certain natural language (block-equality) in Σ2cc is also, unexpectedly, in π2cc.