2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Yao's paper does not cite Kolmogorov directly, but he cites Rabin's Probabilistic Algorithms from Algorithms and Complexity volume, which is dedicated to computational complexity. So yes, he was aware of it. But Kolmogorov aimed at "intrinsic" complexity, rather than information transfers a la Shannon that Yao uses, and the two measures are orthogonal to each other. $\endgroup$ – Conifold Jul 7 '20 at 19:08
  • $\begingroup$ How are they "Orthogonal to each other"? Is it only because Kolmogorov complexity is thought to measure the intrinsic complexity of things? $\endgroup$ – GEP Jul 7 '20 at 20:04
  • 1
    $\begingroup$ "Unlike in 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". $\endgroup$ – Conifold Jul 7 '20 at 20:05
  • $\begingroup$ But still they are both kind of concerned with the amount of information needed to describe an object, either via communication or through a program. Am I wrong? $\endgroup$ – GEP Jul 7 '20 at 20:20
  • 1
    $\begingroup$ Yes, any two things are related if you make it vague enough. $\endgroup$ – Conifold Jul 7 '20 at 20:23
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.