Бригада сборщиков пазла из случайных кусочков: сколько одновременных ходов нужно, чтобы сложить картину? Если кусочки независимы, все кладутся разом. Если каждый следующий зависит от предыдущего, приходится действовать по одному. Так и с системами: одни состояния собираются мгновенно, другие требуют долгой последовательной работы.
Мера, которую предлагает автор, называется параллельной глубиной. Это минимальное число одновременных шагов на компьютере с множеством процессоров, которое нужно, чтобы воспроизвести типичное состояние системы. Для бросания монеты без памяти глубина постоянна: все биты независимы и генерируются одновременно. Для монеты с памятью глубина логарифмическая: произведение независимых множителей можно вычислить методом «разделяй и властвуй».
Другое дело — диффузионно-ограниченная агрегация (рост кластера частиц случайным блужданием). Здесь каждая частица должна дождаться предыдущей, и глубина растёт линейно с числом частиц. Задача генерации такого кластера P-полна: быстрого параллельного алгоритма не существует. Раньше было неясно, как отличить системы, которые просто хранят сложные корреляции, от систем, которые действительно выполняют длинные вычисления. Теперь понятно: глубина мала для процессов с памятью, но велика для последовательных процессов вроде диффузионно-ограниченной агрегации. Мера может применяться для классификации сложных систем в физике, биологии, экономике — везде, где состояния описываются вероятностными распределениями.
Если бы инопланетный исследователь измерял сложность Солнечной системы по энтропии, он бы сосредоточился на Солнце, где сосредоточена почти вся масса и энтропия. Но измерение глубины указало бы на поверхность маленькой планеты Земля — биосферу, чья сложность возникает из долгой эволюционной истории, а не из объёма.