Элементы теории сложности вычислений

Основные понятия и проблемы теории сложности вычислений

Ранее мы рассматривали понятие временной сложности (трудоемкости) алгоритмов. Основным итогом этого рассмотрения явилось понятие оценки сложности алгоритма «в смысле O-большого», т.е. построение выражений T(n) = O(f(n)), характеризующих время работы данного алгоритма при больших N.

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

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

1. Мы рассматриваем массовые, а не индивидуальные задачи. Массовая задача - это класс однотипных задач, различающихся значениями исходных данных (в параграфе 1.2 эти данные назывались параметром p). Например, массовыми являются: задача решения квадратного уравнения (с произвольными коэффициентами), задача раскраски графа (любого заданного). Обозначение z Z означает, что индивидуальная задача z принадлежит классу задач Z (например, Z - задача решения квадратного уравнения, а z - задача решения уравнения 2x² + 5x - 3 = 0).

2. Нас интересует только временная, а не пространственная сложность, причем в смысле максимального, а не среднего времени работы. Далее будем говорить просто «сложность», имея в виду именно эту величину.

3. Мы не претендуем на большую точность оценки, чем «в смысле O-большого». Если же и такую оценку получить затруднительно, то представляет интерес выяснить хотя бы, к какому из двух больших классов относится задача: к полиномиальным или к экспоненциальным. Другими словами, нас интересует, имеется ли для данной задачи какой-нибудь полиномиальный алгоритм (т.е. алгоритм, имеющий оценку сложности O(nk) для некоторого k). Если имеется, то будем говорить, что задача принадлежит классу P (классу полиномиальных задач). Если же удалось доказать, что сложность любого мыслимого алгоритма, решающего данную задачу, растет при больших n быстрее, чем любой полином, то задача принадлежит классу ~P. В принципе, любая задача обязательно принадлежит либо P, либо ~P, однако далеко не для всех задач известно, к какому именно из них.

4. Что должно являться аргументом у «O-большого» в формулах оценки сложности? Выражение «размерность задачи» слишком расплывчато. При теоретическом анализе сложности используется более четкое понятие «длина описания задачи», под которой понимается количество битов информации, необходимое, чтобы выделить из массовой задачи конкретную индивидуальную задачу. Например, для многих задач теории графов описанием задачи может быть матрица смежности конкретного графа или другая форма задания графа. Для задачи решения квадратного уравнения описание задачи – это три коэффициента уравнения, а длина описания зависит от возможного диапазона значений этих коэффициентов. Если используются двухбайтовые целые коэффициенты, то длина описания равна 6 байтам или 48 битам.

Длина описания индивидуальной задачи z Z будет далее обозначаться |z| или l(z).

5. Длина описания может зависеть от способа кодировки данных. В примере с графом очевидно, что разные формы описания одного и того же графа будут иметь разную длину. Принято считать, что все «разумные», т.е. не крайне глупые способы кодировки описания задачи отличаются друг от друга не более, чем полиномиально по длине (т.е. если длины двух описаний равны l и l', то l' = O(lk)), причем время преобразования одной кодировки в другую также полиномиально. Но если так, то полиномиальная задача останется полиномиальной при любом «разумном» способе кодировки, хотя степень полинома может быть разной.

6. Какие вообще алгоритмы считаются допустимыми? Какие операции можно в них использовать? Например, можно ли применять рекурсию? Возможно, какая-нибудь экзотика вроде самомодифицирующейся программы поможет быстро решить задачу, которую «приличные» алгоритмы мусолят очень долго? На самом деле, чем проще, тем лучше (для теоретических доказательств), а потому будем рассматривать только алгоритмы, задаваемые машинами Тьюринга (МТ). Известно, что если на обычном компьютере (машине фон Неймана) алгоритм можно выполнить за число тактов T, то на МТ его можно реализовать за число тактов £ T3. Таким образом, свойство полиномиальности задачи сохраняется при переходе к МТ. Чем хороша эта старая колымага? С одной стороны, она как-никак умеет выполнять любые алгоритмы. С другой стороны, ее легко можно описать, причем описать формально, и с этим описанием потом можно работать, как с данными: вычислять длину описания, преобразовывать и т.п. Это позволяет доказывать теоремы о МТ.

7. Есть большой класс задач, для которых очевидна их экспоненциальная сложность. Это комбинаторные задачи перечисления, упомянутые в параграфе 1.2. Там экспоненциальным является объем выходных данных, а стало быть и время его получения. Вполне уважая эти задачи, мы не будем их рассматривать, ограничившись прежде всего задачами поиска допустимого плана, а также задачами оптимизации.

8.С точки зрения теории, удобно предварительно переформулировать исследуемые задачи в форме задач распознавания, т.е. таких, где требуется ответ «Да / Нет». Например, «Имеется ли маршрут коммивояжера короче 1000 км?» или «Есть ли выигрыш у белых в этой позиции?», или «Связен ли данный граф?». Соответствующая МТ читает свой вход (описание индивидуальной задачи распознавания) и должна придти в одно из двух заключительных состояний, соответствующих «Да» (qy) или «Нет» (qn). Все задачи поиска допустимого плана являются, в сущности, задачами распознавания с вопросом: «Существует ли такой план?» (сам план можно рассматривать как побочный результат решения задачи).

Еще один вопрос: а зачем, собственно, нужно оценивать сложность задачи безотносительно к конкретному алгоритму, имеет ли такая оценка практическое значение? Да, имеет. Она, лучше сказать, имеет большое теоретическое значение для практики. Допустим, нам встретился новый тип задач, их нужно решать, однако других алгоритмов, кроме исчерпывающего перебора, не просматривается. Стоит ли тратить время и умственную энергию на поиск эффективного алгоритма, или же задача объективно сложна, так что ни один точный алгоритм не даст заметного выигрыша по сравнению с перебором, а потому можно только искать суперкомпьютер помощнее или удовлетвориться эвристическим алгоритмом? Оценка сложности задачи помогла бы ответить на этот вопрос.

Вот. Оговорив все это, можно приступать к делу.