HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Proof: Kolmogorov complexity of string concatenation

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
proofconcatenationstringcomplexitykolmogorov

Problem

Does there exist a universal constant $c$ such that for any strings $x, y$, we have: $$K(xy)\leq K(x) + K(y) + c$$
where $K(\cdot)$ denotes the Kolmogorov Complexity of a binary string and $xy$ means the concatenation of $x$ and $y$? I know the answer to this problem is no but I am seeking a proof for this, any hint?

Update: for reference, this is stated at the top of page 266 in Sipser's famous book "Introduction to the Theory of Computation", third edition, and is listed as Problem 6.19 in the book. I've tried to prove it but didn't succeed, just curious to know what proof technique should be used in order to prove it.

Solution

Kolmogorov complexity = length of shortest program to generate a string. Take the program generating x, add the fixed size code that makes it continue with a second program instead of halting, then add the second program generating y.

Context

StackExchange Computer Science Q#88332, answer score: 2

Revisions (0)

No revisions yet.