Extra Problems for Chapter 7

T.M. Cover and J.A. Thomas

1. Kolmogorov complexity

   Assume n very large and known. Let all rectangles be parallel to the frame. No proofs required, but arguments may help provide credit.

   1. What is the (maximal) Kolmogorov complexity of the union of two rectangles on an grid?
      
   2. What if the rectangles intersect at a corner?
      
   3. What if they have the same (unknown) shape?
   4. What if they have the same (unknown) area?
   5. What is the minimum Kolmogorov complexity of the union of two rectangles? That is, what is the simplest union?
   6. What is the (maximal) Kolmogorov complexity over all images (not necessarily rectangles) on an grid?
      

Latex file

Postscript file