×

Determinism vs. nondeterminism in multiparty communication complexity. (English) Zbl 0765.68033

Communication seems to be one of the main computational resources of parallel computing, and to measure the amount of communication performed in parallel computations is as important as to measure time and space complexity of sequential computations. The authors investigate multiparty protocols computing a given Boolean function, where the input is distributed among many computers. The aim is to find a communication strategy (protocol) such that the function can be evaluated with a minimal communication between the computers. The main result shows that no nondeterministic communication protocol can be much more better than the best deterministic one.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI