Бригада сборщиков пазла из случайных кусочков: сколько одновременных ходов нужно, чтобы сложить картину? Если кусочки независимы, все кладутся разом. Если каждый следующий зависит от предыдущего, приходится действовать по одному. Так и с системами: одни состояния собираются мгновенно, другие требуют долгой последовательной работы.

Мера, которую предлагает автор, называется параллельной глубиной. Это минимальное число одновременных шагов на идеализированном компьютере с множеством процессоров, которое нужно, чтобы воспроизвести типичное состояние системы. Глубина не спрашивает, сколько всего вычислений или случайности, — только сколько параллельного времени. Для бросания монеты без памяти глубина постоянна: все биты независимы и генерируются одновременно. Для монеты с памятью глубина логарифмическая: произведение независимых множителей можно вычислить методом «разделяй и властвуй».

Другое дело — диффузионно-ограниченная агрегация (рост кластера частиц случайным блужданием). Здесь каждая частица должна дождаться предыдущей, и глубина растёт линейно с числом частиц. Задача генерации такого кластера P-полна: быстрого параллельного алгоритма не существует. Глубина максимальна: если в большой системе есть одна маленькая, но очень сложная подсистема, глубина всей системы определяется именно ею, а не усреднением по объёму.

Раньше было неясно, как отличить системы, которые просто хранят сложные корреляции, от систем, которые действительно выполняют длинные вычисления. Теперь понятно: глубина мала для процессов с памятью, но велика для последовательных процессов вроде диффузионно-ограниченной агрегации. Мера может применяться для классификации сложных систем в физике, биологии, экономике — везде, где состояния описываются вероятностными распределениями. Главная проблема — глубину нельзя вычислить точно, её можно лишь ограничить сверху, демонстрируя всё более эффективные алгоритмы. Но уже сейчас она помогает увидеть, где в системе спрятаны настоящие вычисления.