С.А. Абрамов - Вычислительная сложность алгоритмов (1123766), страница 12
Текст из файла (страница 12)
Пусть на входеалгоритма сортировки имеется набор чисел 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 .
В этом утверждение есть одна тонкость: новый аргумент f (x) можетиметь другую длину, нежели x , но она тоже будет ограничена полиномиально (т.к. времявычисления ограничено полиномиально).Возникает проблема: верно ли, что P = NP ?Важными понятиями являются NP-трудный и NP-полный предикаты.Определение. NP-трудным называется предикат, к которому полиномиально сводитсялюбой предикат из NP.Определение. NP-полным называется NP-трудный предикат, принадлежащий классу NP.Вырисовывается очень удобный путь для решения обозначенной проблемы вположительном смысле: нужно найти NP-трудную задачу и предложить для неёполиномиальный алгоритм.Доказано, что NP-полной задачей является задача определения выполнимости булевойформулы. Формула является выполнимой, если существует такой набор значенийпеременных, входящих в формулу, что результатом формулы является истина.
Всегоразличных наборов для n переменных будет 2n . До сих пор не известно, существует лиалгоритм, который за полиномиальное время позволяет установить выполнимость, ноизвестно, что задача является NP-полной, а значит NP-трудной.Как уже было сказано, задача о гамильтоновом графе является NP-полной. Это наводит намысль, что P ≠ NP (что, вообще говоря, не доказано и по сей день).Если вы трудитесь над какой-то проблемой и пытаетесь найти для её решенияполиномиальный алгоритм, но вдруг узнаёте, что она является NP-трудной (известная NPзадача полиномиально сводится к вашей), тогда лучше считать, что для вашей задачи нетполиномиального алгоритма.53Для задачи распознавания простоты числа, если входом считать m = ν (n) — битовую длинуn, 3 года назад был предложен Индийский алгоритм (разработанный тремя индийскимиматематиками) с полиномиальной сложностью, допускающий оценку O(m13 ) .
Только длярешения означенной проблемы этот результат ровным счётом ничего не даёт. Если бы имудалось доказать обратное, что не существует полиномиального алгоритма распознаванияпростоты числа, тогда сразу следовало бы, что P ≠ NP , т.к. задача определения простотычисла полиномиально сводится к задаче распознавания составного числа, котораяпринадлежит классу NP.Уместно будет заметить, что мы разнесли задачи распознавания простоты числа ираспознавания составного числа, хотя эти задачи являются обратными. Если для задачиопределения составного числа мы можем показать, что она принадлежит классу NP, то дляобратной задачи распознавания простоты числа мы этого показать не можем (какой тутсертификат?).
Следует отметить, что не обязательно из того, что u ( x) ∈ NP следует, что u(обратная задача к u ) ∈ NP . Поэтому будем говорить, что предикаты, отрицание которыхпринадлежит классу NP, принадлежат классу Co-NP.Отметим, что многие из утверждения, которые мы сделали недавно, доказываются припомощи машины Тьюринга (МТ). Но какое это имеет отношение к нам? А может быть так,когда мы имеем дело с МТ, полиномиального алгоритма нет из-за перемещений по ленте. Вравнодоступной адресной машине (РАМ) таких затрат нет и кажется, что существованиеполиномиальных алгоритмов на РАМ более вероятно.
Но это не так, потому какпутешествия по ленте не очень сильно удлиняют вычисления (в худшем случае сложностьвозведётся в квадрат, но изначально полиномиальная сложность полиномиальной же иостанется). Следовательно, если нет полиномиального алгоритма для МТ, то и для РАМ еготоже нет.Более подробно про алгоритмы полиномиальной сложности и найти более подробныедоказательства сформулированных утверждений можно найти в книге М.Гэри и Д.Джонсона«Вычислительные машины и трудно решаемые задачи».В заключение приведём несколько примеров NP-полных задач.Примеры.1. «Задача редактирования слова».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
