С.А. Абрамов - Вычислительная сложность алгоритмов (лекции) (1121252), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

В этом утверждение есть одна тонкость: новый аргумент 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.

«Задача редактирования слова». Имеется алгоритм A, два слова x, y ∈ A* и k ∈ N .Алгоритм заключается в определении, можно ли из x получить y не более, чем за kопераций, в качестве которых допустимыми являются вычеркивание символа иперестановка двух соседних символов. Доказано, что эта задача NP-полная.2. Имеется квадратная матрица порядка n из нулей и единиц и натуральное число k.Алгоритм заключается в определении, можно ли все единицы покрыть не более чемk прямоугольниками, не покрывая при этом ни одного нуля.

Эта задача тожеявляется NP-полной.3. «Задача о рюкзаке». Задано конечное множество U. Для каждого u ∈ U определёнразмер s (u ) и цена v(u ) . Заданы b, k ∈ N , и спрашивается, можно ли выбратьподмножество U ′ ⊂ U такое, что∑ s(u ) ≤ b , ∑ v(u ) ≥ k .u∈U ′u∈U ′Эта задача тоже является NP-полной.544. Задан набор пар целых чисел (ai , bi ) ∈ Z 2 , i = 1, 2, ... , n , bi ≥ 0 . Рассматриваетсяполином видаn∑a zi =1ibiи спрашивается, есть ли у него корень в комплекснойплоскости, лежащий на единичной окружности ( z = 1 ). Эта задача является NPтрудной, но принадлежность её к классу NP, не установлена.55Задачи1. Доказать равенства:⎢n⎥ ⎡n⎤n = ⎢ ⎥ + ⎢ ⎥ , n∈N⎣2⎦ ⎢2⎥⎡a ⎤ = − ⎣− a ⎦ , a ∈ Rn ⎢n⎥ ⎡n⎤=k==2 ⎢⎣ 2 ⎥⎦ ⎢⎢ 2 ⎥⎥⎢n⎥ ⎡n⎤⎢n⎥⎡n⎤⇒ ⎢ ⎥ + ⎢ ⎥ = k + k = 2k = n .

Если n нечётно, т.е. n = 2k + 1 ⇒ ⎢ ⎥ = k ; ⎢ ⎥ = k + 1⎣2⎦ ⎢2⎥⎣2⎦⎢2⎥⎢n⎥ ⎡n⎤⇒ ⎢ ⎥ + ⎢ ⎥ = k + k + 1 = 2k + 1 = n .⎣2⎦ ⎢2⎥Решение. 1) В случае чётного n решение тривиально: n = 2k ⇒2) Если a ∈ Z , то очевидно, что ⎡a ⎤ = a; ⎣− a ⎦ = − a , что доказывает равенство. Если a неявляется целым, то найдется такое целое число n и такое 0 < ε < 1 , что a = n + ε .

Тогда⎡a ⎤ = ⎡n + ε ⎤ = n + 1 , ⎣− a ⎦ = ⎣− n − ε ⎦ = −n − 1 ⇒ ⎡a ⎤ = − ⎣− a ⎦ .2. Доказать равенство:k , n ∈ N, k > 1 ⇒ ⎣log k n ⎦ + 1 = ⎡log k (n + 1)⎤Решение. Не трудно видеть, что для данного n всегда найдётся такое целое число m,что выполняется оценка: k m ≤ n < k m+1 . Тогда ⎣log k n ⎦ = m . Так как k целое, тоk m < n + 1 ≤ k m+1 , откуда m < log k (n + 1) ≤ m + 1 ⇒ ⎡log k (n + 1)⎤ = m + 1 что и доказываетравенство.3. Считая в алгоритме сортировки простыми вставками операцию обмена a ↔ bреализованной следующим образом: с := a; a := b; b := c, определить, чемуравны TI1 и TI 2 .4.

Имеется железнодорожный разъезд с тупиком (см. рис.), в одной части которогонаходятся 2n вагонов двух типов: n белых и n чёрных. Порядок вагонов не определён.Имеется 3 операции перемещения вагонов: 1) МИМО, 2) В (в тупик) и 3) ИЗ (из тупика).Требуется привести алгоритм сортировки вагонов, в результате работы которого сдругой стороны будет составлена последовательность из 2n вагонов, цвета которыхчередуются.МИМОИЗ2nВРешение. Требуется переправить вагоны справа на лево, изменив их порядок так,чтобы цвета вагонов чередовались. Предлагаемый алгоритм заключается в следующем:если цвет первого вагона формируемого состава не имеет значения, то первый вагонпросто проходит МИМО.

Если цвет первого вагона важен, то с помощью тупика этовсегда можно сделать. Далее, пока имеются вагоны справа, проверяем на совпадениецветов последний вагон слева с первым вагоном справа. Если их цвета не совпадают,56выполняем операцию МИМО, после чего проверяем наличие вагонов в тупике. Если втупике имеются вагоны, то выполняем операцию ИЗ и переходим к следующемувагону справа. При совпадении цветов, отправляем очередной вагон в тупик операциейВ.На псевдокоде предлагаемый алгоритм выглядит следующим образом: исходныйсостав справа обозначен массивом ai, каждый элемент которого принимает значениячёрный или белый.

Операция not меняет значение цвета с белого на чёрный инаоборот, z — текущее количество вагонов в стеке, k — цвет последнего вагонаформируемого состава слева. Основная идея алгоритма заключается в том, что в тупикев один момент времени не могут находиться вагоны разных цветов и в конце каждойитерации цикла если в тупике есть вагоны, то цвет их совпадает с цветом последнеговагона формируемого состава.z := 0; k := a1;for i = 2 to 2n doif k = ai thenВ;z := z + 1;elseМИМО;k := ai;if z > 0 thenИЗ;z := z – 1;k := not k;fifiodНе трудно видеть, что сложность представленного алгоритма по количеству операцийМИМО, В, ИЗ T = O(n) , но из постановки задачи ясно, что сложность любогоалгоритма, решающего задачу, есть Ω(n) , следовательно, сложность представленногоалгоритма T = Θ(n) .5. Путник стоит перед бесконечной стеной в обе стороны.

Известно, что на расстоянии nшагов в одну из сторон находится дверь. Требуется привести алгоритм нахождениядвери путником, сложность которого по числу шагов составляла бы O(n) .Решение. Очевидный алгоритм заключается в следующем: путник на первой итерацииделает один шаг в одну из сторон, затем возвращается и делает один шаг уже в другуюсторону и снова возвращается. На второй итерации ситуация повторяется, но ужесовершается по два шага в обе стороны. На третьей итерации — три шага и т.д. пока небудетобнаруженадверь.Сложностьтакогоалгоритмасоставляет22 ⋅ (1 + 2 + ...

Характеристики

Список файлов лекций