С.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (1121252), страница 11
Текст из файла (страница 11)
Деление в этом случае будет неточным, поэтому надо выполнитьbbделение с запасом ( 3m ), после чего умножить. При этом младшие разряды могутоказаться неверными. Дотошные люди посчитали, что их количество не превосходит 3,и «шевелением» этих разрядов можно получить точный ответ. Осталось показать, чтоR ≤ D , но это очевидно.Определение. Пусть существуют 2 задачи P и Q и 2 алгоритма U и V такие, что алгоритм Uпо входу задачи P строит один или несколько входов для задачи Q:Uy1 , ...
, yk — входы Qx — вход P ⎯⎯→Задача Q переводит y1 , ... , yk в z1 , ... , zk : Q( y1 , ... , yk ) → z1 , ... , zk , а алгоритм V по z1 , ... , zkстроит решение задачи Q. Тогда пару (U , V ) будем называть сведением.Отвлечёмся на минуту от сведений и докажем общее утверждение.Утверждение. Если P и Q таковы, что P ≤ Q , P и Q — классы алгоритмов, решающихзадачи P и Q соответственно, и пусть f (n) — асимптотическая нижняя граница сложностидля класса P. Тогда f (n) будет являться асимптотической нижней границей сложности длякласса Q.(Доказательство: P ≤ Q ⇔ TAP (n) = O TAQ (n))()⇔ TAQ (n) = Ω TAP (n) . С другой стороны,f (n) является асимптотической нижней границей для P ⇒ ∀A ∈ P (в частности, дляA = AP ) будет верна оценка: TA (n) = Ω( f (n) ) ⇒ TAP (n) = Ω( f (n) ) ⇒ TAQ (n) = Ω( f (n) ) , чтодоказывает утверждение.Пример.
Вернёмся к задаче построения выпуклой оболочки. Покажем, что если за размеравхода взять n — количество данных точек на плоскости, то Ω(n log n) будет нижнейасимптотической оценкой. Отметим, что «продвинутые» алгоритмы построениявыпуклой оболочки имеют оценку сложности O(n log n) , тем самым являютсяоптимальными по порядку сложности. Как показать Ω(n log n) ? Для этого сведёмалгоритм сортировки к задаче о построении выпуклой оболочки. Пусть на входеалгоритма сортировки имеется набор чисел x1 , x2 , ... , xn . Построим по ним набор точек()()()на плоскости следующим образом: x1 , x12 , x2 , x22 , ...
, xn , xn2 .xi2xiОчевидно, что все точки будут принадлежать выпуклой оболочке. Теперь, если мызахотим её выдать в виде упорядоченного массива вершин с обходом, например, по50часовой стрелке, то нам непременно потребуется отсортировать начальные значенияx1 , x2 , ... , xn . Мы уже знаем, что Ω(n log n) является асимптотической оценкой снизудля алгоритмов сортировки, поэтому для алгоритмов построения выпуклой оболочкибудет верна оценка Ω(n log n) . Таким образом, если известно, что одна задача решаетсямедленно, то, сведя другую задачу к первой, можно показать, что она тоже решаетсямедленно.Рассмотрим две задачи: умножение булевых матриц и транзитивно-рефлексивное замыканиеграфа.
Можно показать, что эти задачи являются эквивалентными. Таким образом, если мынаучимся находить транзитивное замыкание за O(n 2 ) , то и булевые матрицы мы сможемумножать за O(n 2 ) .Действительно, если A — матрица смежности исходного графа (A порядка n), тогда матрицасмежности транзитивно-рефлексивного замыкания графа будет равнаA* = I ∨ A ∨ A2 ∨ ... ∨ An = (I ∨ A) (максимальная длина пути — n)nПусть у нас есть две матрицы: A и B. Построим по ним ещё одну матрицу по следующемуправилу:⎡0⎢0⎢⎢⎣0A000⎤B ⎥⎥0 ⎥⎦и рассмотрим граф, для которого эта матрица будет являться матрицей смежности. Теперьпосмотрим, что будет транзитивно-рефлексивным замыканием этого графа.
Замыканиембудет граф со следующей матрицей смежности:⎡I⎢0⎢⎢⎣0A AB ⎤IB ⎥⎥0 I ⎥⎦Тем самым, для получения произведения AB достаточно прочитать верхний правый уголполучившейся матрицы.Обычно для построения транзитивно-рефлексивного замыкания используют алгоритмУоршела со сложностью O (n3 ) , где за O скрывается совсем не большая константа (порядка3), и ещё одним преимуществом алгоритма является небольшой расход памяти.Далее нашей целью будет рассмотрение некоторых вопросов алгоритмов полиномиальнойсложности.
Для таких алгоритмов сложность не обязательно является полиномом, но тем неменее она должна допускать оценку O(n c ) , где c — некоторая константа. Вообще говоря,оценка с O предполагает выполнение соответствующего неравенства начиная с некоторого n,но мы будем считать, что для всех n выполняется T (n) ≤ p(n) , где p(n) — полином.Полиномиальной сложности алгоритмы — это искусство. Вопрос существованияполиномиального алгоритма, решающего ту или иную задачу, отнюдь не праздный. Отэкспоненциальной сложности стараются перейти к полиномиальной.
Сторонники получениякакого-нибудь алгоритма не стремятся получить алгоритм с полиномиальной сложностью.Основной своей задачей они считают получение алгоритма, а снижение показателясложности — это вопрос времени.Рассмотрим следующий пример. В линейном программировании существует симплексметод, позволяющий решать задачи, сложность которого не является полиномиальной.Несколько лет назад был найден алгоритм решения задач линейного программирования с51полиномиальной сложностью, но коэффициенты полинома были настолько велики, чтоникакого продвижения не было. Симплекс-метод обладает субэкспоненциальнойсложностью: растёт медленнее, чем d n , но быстрее, чем любой полином.
Например,субэкспоненциальной будет сложность, имеющая вид n log n . Тем не менее, дело-то в том, чтосложно, глядя на задачу, определить, имеется ли полиномиальный алгоритм её решения илинет.Сосредоточимся на задачах распознавания, т.е. задачах, ответом на которые является «да»или «нет».
Более конкретно рассмотрим задачу распознавания языков, которая ставитсяследующим образом: есть некоторый алгоритм A, множество слов в алфавите A обозначимчерез A* и выбирается их подмножество L ⊂ A* — язык в алфавите A. Оговорим ещё однодопущение: что брать за размер входа? Для массивов мы брали число элементов, дляквадратных матриц — порядок (что не то же самое, что число элементов). Здесь входомбудут слова x, а за размер входа возьмём его длину x — число букв в этом слове(неотрицательное целое).
Определимся с операциями. Т.к. любой конечный алфавит можносвести к A = {0, 1} (все слова в алфавите A можно кодировать последовательностями изнулей и единиц). Тогда в качестве операций можно рассматривать битовые операции ибитовую сложность. Не обязательно рассматривать двухсимвольный конечный алфавит,можно и более богатый, только операции в этом случае будут задаваться соответствующимитаблицами. Примечательно, что таким способом суженная задача вызывает проблемы болееосязаемые и более привычные.Пусть алгоритмы распознавания языков, имеющие полиномиальную сложность, образуюткласс P.
В некоторых изданиях к P относят все алгоритмы с полиномиальной сложностью,что было бы не совсем правильным. Класс полиномиальных алгоритмов правильнее было быобозначить через Poly. Вернёмся к нашему определению класса P, как классу алгоритмовраспознавания имеющих полиномиальную сложность. Задача определения принадлежностиалгоритма к классу P является достаточно сложной.Нас будут интересовать предикаты, определённые на словах.
Можно говорить не о «задачах»из класса P, а о предикатах.Рассмотрим наряду с P другой класс алгоритмов — NP.Определение. Будем говорить, что предикат (задача) u ( x) ∈ NP , если существуют такиеполиномы p и q и такой предикат R ( x, y ) , что u ( x) = ∃ y∈A* , y ≤ p ( x )R( x, y ) и предикат R ( x, y )имеет полиномиальную временную сложность, ограниченную q ( x + y ) .Соотношение для u (x) можно записать и в другой форме: ∃ y∈A* ( y ≤ p( x ) ∧ R( x, y ) ) .Обозначение NP происходит от non deterministic polynomer. Слово y в этом случаеназывается сертификатом x (в некоторой литературе — «подсказкой»).Класс NP замечателен тем, что легко проверить принадлежность к нему.
Рассмотрим это напримерах. Но для начала мы должны определится с тем, как будем записывать слова внашем алфавите. Эти способы, вообще говоря, могут быть весьма разнообразными. Дляпримера рассмотрим ситуацию, когда алфавитом являются целые положительные числа. Вэтом случае для их записи мы можем использовать палочную систему (рисовать столькопалочек, какое число мы хотим изобразить) или позиционную систему счисления.Сложность в разных случаях будет различной.Рассмотрим задачу определения, является ли заданный граф гамильтоновым.Гамильтоновым называю граф, если в нём существует путь, проходящий через все вершиныровно по одному разу.
Когда мы рассматриваем произвольный граф и хотим определить,является ли он гамильтоновым, мы можем записать граф матрицей смежности (при52необходимости разделяя строчки некоторым разделителем). Не трудно видеть, чтосформулированная задача распознавания гамильтонового графа принадлежит классу NP.Чтобы доказать это достаточно указать сертификат, в качестве которого в данном случаеможно взять сам гамильтонов путь. Уж как-нибудь за не очень большое (полиномиальное)время проверить, является ли он путём и является ли он гамильтоновым, мы вполне сможем.Задача определения составного числа так же принадлежит классу NP.
Сертификатом в этомслучае будет делитель. Очевидно, что за короткое время мы сможем проверить, является лион делителем или нет.Отметим ещё, что на вход алгоритма распознавания наряду с корректными данными могутподаваться некорректные, например какая-нибудь белиберда. Но задача проверкикорректности введённой информации решается за полиномиальное время, поэтому, неограничивая общности, можно считать, что на вход нам всегда подаются корректные данные.Важным понятием является понятие полиномиальной сводимости.Определение.
Будем говорить, что задача (предикат) u1 полиномиально сводится к задачеu2 , если существует функция f : A* → A* , применимая к любому слову из A* , времявычисления которой ограничено p0 ( x ) , и такая, что истинность u1 ( x) эквивалентнаистинности u2 ( f ( x) ) .Обозначение: u1 ≤ P u2Необходимо отметить важный момент: если u1 полиномиально сводится к задаче u2 иu2 ∈ P , тогда u1 ∈ P .