Communication complexity of multi-processor systems (Q1118403)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4094804
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Communication complexity of multi-processor systems |
scientific article; zbMATH DE number 4094804 |
Statements
Communication complexity of multi-processor systems (English)
0 references
1989
0 references
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.
0 references
multi-processor systems
0 references
Las Vegas computations
0 references
nondeterministic computations
0 references
communication complexity
0 references
communicating processors
0 references
0.8035088777542114
0 references
0.7774574756622314
0 references
0.7764337062835693
0 references
0.7759000658988953
0 references
