Communication complexity of multi-processor systems (Q1118403)

The communication complexity model of two communicating processors [\textit{H. Abelson}, J. Assoc. Comput. Mach. 27, 384-392 (1980; Zbl 0438.68009); \textit{Ch. Papadimitriou} and \textit{M. Sipser}, Communication complexity. J. Comput. Syst. Sci. 28, 260-269 (1984; Zbl 0584.68064); \textit{A. C. Yao}, Some complexity questions related to distributive computing, in: Proc. 11th ACM STOC, ACM, 209-213 (1979)], is generalized to a model consisting of k processors connected by a common bus. A lower bound technique used for the original communication complexity is extended for k-processor model and it is shown that the deterministic communication complexity cannot differ more than quadratically from the nondeterministic complexity.