Комбинаторный смысл утверждений о сложности. Мы приведём один пример такого рода (подробнее см. главу 10, с. 348). Существует неравенство для [колмогоровских] сложностей трёх слов и их комбинаций:
для любых трёх слов
длины не больше
.
Оказывается, что это неравенство имеет естественные интерпретации, в которых
о сложности уже ничего не говорится. В частности, из него можно вывести такой
геометрический факт [51].
Пусть имеется тело в трёхмерном пространстве с перпендикулярными осями
и
, имеющее объём
. Рассмотрим три его ортогональные проекции на плоскости
, и
. Пусть
и
- площади этих проекций. Тогда имеет место такое неравенство:
...
Докажите аналогичное неравенство для любого числа случайных величин:
(В правой части неравенства складываются энтропии кортежей, состоящих из всех случайных величин, кроме одной.)
...
Покажите, что из неравенства задачи 229 следует оценка для объёма
-мерного тела через объемы его
-мерных проекций (обобщение неравенства,
упомянутого на с. 21): объем тела, возведенный в
-ю степень, не превышает произведения
-мерных объемов его проекций на координатные гиперплоскости. [Указание. Сначала докажите неравенство для тел, составленных из единичных кубиков. Для этого рассмотрите случайную величину, равномерно распределенную среди кубиков, составляющих тело. Для общего случая надо перейти к пределу, разбивая тело на кубики.]
Это неравенство является частным случаем более общего геометрического неравенства Лумиса Уитни [85].