CS代考计算机代写 Kolmogorov complexity

Kolmogorov complexity
Let 𝑠 be a finite string of bits of length 𝑛. Define 𝐾(𝑠) as the number of bits in the shortest program that prints 𝑠. Note that 𝐾(𝑠) ≤ 𝑛 (not counting additive terms). When 𝐾(𝑠) = 𝑛 we say that 𝑠 is Kolmogorov random. The idea is that compressible strings (those that have Kolmogorov programs shorter than themselves) contain patterns of some kind and these can be used to compress the string.
Define 𝐾(𝑠|𝑡) to be the number of bits in the shortest program that, given 𝑡 as input, prints 𝑠.
Assume that an AES key 𝑘 containing 𝑛 bits is randomly generated so 𝐾(𝑘) = 𝑛. One can see that every sub-key 𝑘𝑖, each of those also of length 𝑛, can be easily generated by a program given 𝑘 as input. Therefore 𝐾(𝑘𝑖|𝑘) = 𝑐, where 𝑐 is the size of a program that generates the AES key schedule. But also note that 𝐾(𝑘|𝑘𝑖) = 𝑑, where 𝑑 is the size of another program that can find an AES key given one of the sub-keys.
By this, we have that 𝐾(𝑘𝑖) = 𝐾(𝑘). If this were not true
and 𝐾(𝑘𝑖) were smaller, then I could combine the short program for printing 𝑘𝑖 with the constant sized program that, given 𝑘𝑖 , prints 𝑘 and so would have a program with fewer than 𝑛 bits to print 𝑘, contradicting the fact that it was chosen to be a random string.