TransWikia.com

Did Kolmogorov complexity influence the development of communication complexity?

History of Science and Mathematics Asked on September 2, 2021

I was reading a wikipedia article about communication complexity and it seems to me that it bears some resemblance to Kolmogorov complexity.
Was the founder of communication complexity influenced by Kolmogorov complexity?

One Answer

The first link says that

communication complexity studies the amount of communication required to solve a problem when the problem is distributed between two or more parties.

Whilst the second link says that

Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program... that produces the object as output. It is a measure of the computational resource...

Had you read further down in the first link you would have discovered:

Note that unlike computational complexity theory, communication complexity is not concerned with the amount of computation performed by Alice or Bob, or the size of the memory used, as we assume nothing about the computational power of Alice or Bob.

So, no, the two concepts are not at all related other than sharing the word 'complexity' in their names. And that connection is spurious.

Answered by Mozibur Ullah on September 2, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP