3.3. Параметризованная сложность

Ранее мы рассматривали сложность алгоритма (или задачи) как функцию  = f(V) одной переменной. В качестве этой переменной рассматривался объем (сложность) исходных данных. Во многих случаях при таком подходе может быть получен точный результат. Например, сложность вычисления скалярного произведения векторов длины V, сложность перемножения квадратных матриц размера V.

Но также мы знаем, что для ряда задач сложность данных (по отношению к алгоритму) невозможно охарактеризовать одним параметром так, чтобы получалась функциональная зависимость  = f(V). Например, алгоритм упорядочения массива чисел из V элементов будет выполнять различное число шагов, зависящее не только от значения V, но и от того, как числа расположены перед началом работы алгоритма. Как правило, для многих реальных алгоритмов упорядочение чисел, уже расположенных в нужном порядке, требует гораздо меньше времени, чем упорядочение чисел, расположенных первоначально в обратном порядке. Сложность решения задачи изоморфизма графов зависит не только от количества V вершин в графе, но и от количества ребер W, и от ряда других характеристик.

В таких случаях обычно вводятся две функции сложности – нижняя граница и верхняя граница. Чаще всего они имеют разный порядок роста, поэтому неясно, на что ориентироваться при сравнении нескольких алгоритмов, решающих одну и ту же задачу. Тогда вводится средняя оценка сложности на основе вероятностного подхода. Не преуменьшая ее теоретического значения, все-таки мы вправе задаться вопросом: а какую пользу она принесет в определении количества шагов алгоритма для вполне конкретных (не случайных) исходных данных?

Точное решение проблемы оценки сложности можно искать на пути характеризации исходных данных набором параметров,  = f(p₁ , p₂ , …, p_n). Конечно, и здесь много подводных камней. Фактически, нам требуется любые данные (и не числовые тоже) характеризовать конечным набором чисел. Даже из общетеоретических соображений ясно, что в общем случае это невозможно. В качестве примера можно снова привести задачу определения изоморфизма графов. Однозначное кодирование графа конечным набором чисел означало бы, что мы решили задачу отыскания полного набора инвариантов графа, не зависящего от его размера. В теории графов эта задача не решена.

Правда, однозначная идентификация не требуется – достаточно, чтобы набор параметров разделял графы на классы с одинаковой сложностью по отношению к исследуемому алгоритму. Но здесь возникает новая проблема – для разных алгоритмов, решающих одну и ту же задачу, мы будем получать функции сложности, зависящие, может быть, от разных наборов параметров. Следовательно, мы не сможем сравнивать между собой и эти функции, и эти алгоритмы.

Тем не менее, безуспешные попытки решить проблему P =? NP вынуждают исследователей рассматривать функции сложности двух переменных  = f(V, k). Такую оценку называют параметризованной сложностью. Задача состоит в том, чтобы выяснить, где скрываются истоки экспоненциальной сложности некоторых задач и, возможно, показать, что по важному параметру V сложность полиномиальна, а экпоненциальная зависимость проявляется по отношению к «второстепенному» параметру k.