5
$\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$
6
  • 4
    $\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, 2020 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, 2020 at 20:04
  • 2
    $\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, 2020 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, 2020 at 20:20
  • 1
    $\begingroup$ Yes, any two things are related if you make it vague enough. $\endgroup$
    – Conifold
    Jul 7, 2020 at 20:23

2 Answers 2

3
$\begingroup$

As pointed out by Conifold in the comments, the answer of the history seems likely that Yao was surely aware of Kolmogorov complexity at the time, but that the introduction of communication complexity was more motivated by communication between agents or processors than any connection with Kolmogorov complexity.

That said, there are some relations between the two concepts, for example:

$\endgroup$
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 and acknowledge you have read our privacy policy.

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