For sufficiently large |w|, how many of the 2^|w| strings of length |w| are entirely unrelated?

A way to define this: two strings are unrelated if their joint Kolomogorov complexity is practically equal to their individual Kolmogorov complexities added together: K(w1,w2)=K(w1)+K(w2)

  • 1
    $\begingroup$ It doesn't make sense to ask "How many items are Y" if Y is a binary relationship between two items; that only makes sense if Y is a property of a single item. Are you looking for the maximum-sized subset of $\{0,1\}^{|w|}$ such that all pairs in the subset are unrelated by that definition? $\endgroup$
    – D.W.
    Nov 25 '20 at 23:44
  • 1
    $\begingroup$ The answer could potentially depend on which universal mechanism is used to define $K$. $\endgroup$ Nov 26 '20 at 22:27
  • 1
    $\begingroup$ @YuvalFilmus two incompressible strings of a given length cannot be related by this K(w1,w2)=K(w1)+K(w2) as it would break that rule --since most strings are incompressible most are unrelated. Is this along the lines of an answer? How much could choice of K vary the answer--not more than a constant right? $\endgroup$
    – user122281
    Nov 27 '20 at 3:46
  • $\begingroup$ The choice of $K$ varies the Kolmogorov complexity by at most a constant. $\endgroup$ Nov 27 '20 at 4:51

This site is temporarily in read only mode and not accepting new answers.