Сложность булевых схем (Circuit Complexity): Архитектура вычислений
Когда мы оцениваем алгоритмы нотацией О-большое (O(N)), мы представляем Машину Тьюринга, которая последовательно выполняет код, считывая ленту туда и обратно. Но современные микропроцессоры работают иначе: это гигантские статичные графы из миллиардов транзисторов, по которым ток пробегает практически мгновенно. Для анализа аппаратной эффективности дискретная математика использует совершенно другую метрику — Сложность булевых схем.
Булева схема — это направленный ациклический граф (DAG). Его узлы-листья — это входные биты данных (0 или 1), а внутренние узлы — это логические вентили (И, ИЛИ, НЕ). Эффективность такой схемы математически описывается двумя главными параметрами:
- Размер схемы (Size): общее количество логических вентилей. Это эквивалентно площади, которую чип займет на кремниевой пластине.
- Глубина схемы (Depth): самый длинный путь (в количестве вентилей) от любого входа до выхода. Глубина — это критический параметр времени. Сигнал не может пройти схему мгновенно, каждый вентиль имеет физическую задержку. Чем меньше глубина, тем на более высокой тактовой частоте (ГГц) сможет работать процессор.
В теории сложности схем выделяют класс NC (Nick's Class), названный в честь математика Ника Пиппенджера. Класс NC включает задачи, для которых можно построить схему полиномиального размера (разумного количества транзисторов) с полилогарифмической глубиной (O(log^k N)). Задачи из класса NC считаются эффективно распараллеливаемыми. Сложение, умножение двоичных чисел и сортировка матриц лежат в классе NC.
Напротив, существуют P-полные задачи (например, вычисление максимального потока или задача линейного программирования). Математики предполагают, что для них невозможно создать "неглубокую" схему. Это означает, что даже если мы дадим вам процессор с миллиардом независимых ядер (суперкомпьютер), вы не сможете решить эти задачи быстрее, чем на обычном одном ядре, так как каждый следующий шаг жестко зависит от завершения предыдущего.
Апогеем теории сложности схем являются доказательства нижних оценок Шеннона. Клод Шеннон доказал, что почти все мыслимые булевы функции от N переменных требуют схемы экспоненциального размера O(2^N / N). Это значит, что для большинства математических задач невозможно создать физический микрочип, который вычислял бы их ответ за один такт!
