На этом шаге мы рассмотрим основные понятия сложности задач.

Под задачей понимается некоторый вопрос, на который нужно найти (вычислить) ответ. Задачи бывают общие (массовые - сравните со свойством алгоритма) и частные (индивидуальные). Общая задача определяется:

списком параметров - свободных переменных, конкретные значения которых не определены;
формулировкой условий - свойств, которыми должен обладать ответ (решение задачи).

Частная задача получается из общей задачи, если всем параметрам общей задачи придать конкретные значения (задать исходные данные). Для алгоритма сказали бы: на место формальных параметров подставить фактические.

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

Тем не менее, сложность задачи (чисто математической или естественнонаучной, выраженной с помощью некоторого формального языка) представляется одной из фундаментальных характеристик в познании той Вселенной, в которой мы существуем. Характеристикой не менее значимой, чем физические константы - скорость света в вакууме, постоянная Хаббла (значение плотности вещества во Вселенной, разделяющее замкнутую и открытую космогонические модели); чем известные математические константы и др.

Компьютерные науки делают пока только первые шаги в классификации задач по сложности. Естественно, что начинаем с дихотомии: попытки разделить все задачи на два класса - легкие и трудные. Границу между ними можно проводить по-разному, но все сошлись во мнении, что задачи, для решения которых требуется выполнить O(n), O(n²), O(n³), ... операций - это легкие задачи (здесь n - параметр сложности исходных данных). Задачи же с оценкой сложности O(2ⁿ) и более - сложные. Первую группу задач называют задачами полиномиальной сложности, поскольку их временная сложность ограничивается сверху некоторым полиномом (быть может, очень большой, но конечной степени n). Обозначим множество таких задач Р. Вторую группу называют задачами экспоненциальной сложности, поскольку в общем случае (т. е. для исходных данных, наиболее "неудобных" для любого из алгоритмов, решающих задачу) требуется количество операций, увеличивающееся с ростом n, по крайней мере, экспоненциально. Обозначим множество этих задач ЕХР.

Такое разграничение практически оправдано. Представим себе, что на самом быстром из доступных нам компьютеров решаем две задачи, полиномиальную Р₁ с параметром сложности исходных данных и, и экспоненциальную Р₂ с параметром n₂. Эти две задачи решаются примерно одинаковое время T и находятся на грани того, чтобы испытывать наше терпение: согласны ждать время T, но ни секунды больше! И вот, наконец, мы получили новый компьютер, работающий в несколько (k) раз быстрее, чем старый. Вопрос: насколько более сложные задачи можно решать на новом компьютере (как изменятся n и n²?), если наши возможности ожидания решения не изменились?

Простой анализ показывает, что доступная сложность полиномиальной задачи увеличилась В несколько раз, стала равной m*n₁, а доступная сложность экспоненциальной задачи увеличилась на несколько единиц, стала равной n₂+l. Здесь m и l вычисляются через k. Например, если первая задача имеет линейную сложность, а вторая - 2ⁿ, то ускорение компьютера в два раза (k=2) приводит к значениям 2n₁ и n₂+l. Это действительно качественно различные результаты.

Известны многие представители класса задач полиномиальной сложности:

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

Хотелось бы, чтобы все задачи были легкими, но сегодня для ряда задач известны только экспоненциальные алгоритмы! В связи с попыткой классификации сразу возникает много вопросов. Существуют ли неполиномиальные задачи или для любой задачи может быть построен полиномиальный алгоритм? Если существуют, то где проходит граница между полиномиальными и неполиномиальными задачами, как ее описать (иными словами, найти легко вычислимую характеристическую функцию множества Р)?

Для ответа на эти и другие вопросы нужно навести порядок в множестве задач, выделить некоторые полезные типы задач (так называемые переборные задачи) и ввести хотя бы минимальную формализацию. Кроме этого понадобится:

Понятие сложности исходных данных. Нам необходим универсальный подход, не зависящий от семантики той или иной задачи. За универсальность приходится платить и плата состоит в том, что не будем получать точные оценки сложности задач, а лишь делать утверждения о виде зависимости (линейная, квадратичная и т.д.).
Понятие сведения одной задачи к другой. Положим, у нас есть решающий некоторую задачу алгоритм; можно ли его использовать для решения другой задачи, а если можно, то как? Как при этом связаны сложности этих двух задач? В качестве примера такого сведения можно привести задачи вычисления обратной матрицы и решения системы линейных уравнений. Алгоритм решения первой задачи может быть использован для решения второй задачи, но при этом потребуются некоторые дополнительные вычисления. Как известно, обе задачи имеют полиномиальную сложность. Сведение одной задачи к другой - это тоже задача! И в данном случае она также имеет полиномиальную сложность. Эту ситуацию обозначают следующей фразой: первая задача полиномиально сводима ко второй задаче. Позже будут даны более точные определения.
Понятие инвариантности вычислителя (компьютера) к классу задач. Хотелось бы, чтобы вычислитель, в терминах команд которого оценивается сложность, не влиял на результаты классификации задач. Изменение (в разумных пределах) архитектуры, системы команд, способов представления данных не должно перемещать задачу из одного класса в другой, хотя временные функции сложности будут, конечно, различными.
Два понятия, относящиеся к процессу решения задачи: детерминированное вычисление и недетерминированное вычисление. Детерминированное вычисление - обычный, классический способ (это понятие входит в определение алгоритма как одно из свойств). Недетерминированное вычисление имеет более общий характер: обычно оно ведет себя как детерминированное, но на некоторых шагах вдруг "размножается" и начинает существовать в двух или более параллельно работающих экземплярах, т. е. имитирует исполнение на многопроцессорной вычислительной машине с неограниченным количеством процессоров. Ясно, что распараллеливание работы может уменьшать время вычислений. Но насколько? Может ли распараллеливание перевести задачу из одного класса сложности в другой? Ответ не очевиден. Возьмем в качестве примера задачу поиска элемента в бинарном дереве, причем в множестве ключей поиска не определено никакого отношения порядка. Это означает, что в худшем случае нужно посетить все n вершин. Если просмотр распараллелить, начиная с корня, одновременно просматривая левое и правое поддеревья, а внутри каждого из поддеревьев процессы вновь распараллелить и т.д., перемещаясь по ссылкам к концевым вершинам, то нам потребуется время, пропорциональное log₂(n) и количество процессоров, пропорциональное n. Таким образом, соотношение времен детерминированного и недетерминированного вычислений такое же, как и соотношение экспоненциального и линейного алгоритмов (если считать параметром сложности исходных данных количество уровней дерева), т. е. при распараллеливании задача переходит из одного класса в другой. Известно, что существуют плохо распараллеливаемые задачи, для которых увеличение количества процессоров сверх некоторой константы не приводит к уменьшению времени вычислений. Такие задачи, очевидно, останутся в своем классе при изменении способа вычисления.

На следующем шаге мы рассмотрим понятие переборной задачи (задачи, решаемой методом полного перебора).

Содержание Следующий шаг