Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 42

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

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

Пусть TfPAM (n) < p(n), гдеp — некоторый полином. Тогда количество ячеек, используемых fPAMпри работе со словом x, сверх тех, в которых изначально хранится x, не превосходит Cp(| x |) при некоторой положительной констанСм., например, [, разд. ], [, разд. .]. Впервые эта теорема была доказана,вероятно, М. Блюмом.См. [, разд. .].Глава . Сводимостьте C. Если использовать МТ вместо РАМ, то возникающие дополнительные затраты на переходы от одной ячейки ленты к другой можно сделать меньшими, чем | x | + Cp(| x |) при каждой битовой операции. Таким образом, общее число тактов работы МТ не превзойдетp(| x |)(| x | + Cp(| x |)), и сложность вычислений на МТ будет ограничена полиномом p(n)(n + Cp(n)).§ .

Полиномиальная сводимость. NP-полные задачиОдна и та же математическая задача распознавания может быть формализована с использованием разных алфавитов и разных способовкодирования. Тем не менее, если речь, например, идет о некоторой арифметической задаче, то можно ожидать, что основание q ∈ N,q ¾ 2, выбранной позиционной системы счисления не будет влиятьна принадлежность соответствующего предиката классу P, так какразмеры ⌈logq1 (n + 1)⌉, ⌈logq2 (n + 1)⌉ записей числа n в двух разныхсистемах счисления являются величинами одного порядка, и сам переход от одной записи к другой может быть выполнен за время, ограниченное полиномом от размера входа.Такого рода связь может существовать и между совершенно разными задачами распознавания, формализованными с помощью предикатов на словах.Определение ..

Пусть v и ṽ — предикаты на словах в алфавитахe . Говорят, что v полиномиально сводится к ṽ, и пишут v ¶ p ṽ, еслиΛ, Λe ∗ , что v(x) = ṽ( f (x)).существует такая функция f ∈ P, f : Λ∗ −→ ΛИз того, что для f ∈ P длина слова f (x) как функция от длины слова x полиномиально ограничена, а также из того, что композиция двух полиномов p3 (t) = p1 (p2 (t)) вновь является полиномом(при этом если p1 (t), p2 (t) имеют неотрицательные коэффициенты,то и p3 (t) тоже), мы получаем, что отношение ¶ p транзитивно и чтоṽ ∈ P =⇒ v ∈ Pпри v ¶ p ṽ.В -х годах прошлого столетия С.

Кук доказал замечательную теорему о существовании в NP таких предикатов на словах, к каждомуиз которых полиномиально сводится любой предикат из NP. Принятая терминология такова:Определение .. Предикат u ∈ NP называется NP-полным, еслиv ¶ p u для каждого v ∈ NP.§ . Полиномиальная сводимость. NP-полные задачиПеред формулировкой теоремы Кука напомним, что любую булевуформулу от x1 , x2 , ..., xn можно задать в конъюнктивной нормальнойформе (КНФ):D1 ∧ D2 ∧ ... ∧ Dm ,Di = (li1 ∨ li2 ∨ ... ∨ li,ki ),i = 1, 2, ..., m,(.)при этом lij является литералом, т. е.

некоторой переменной x s илипеременной с отрицанием ¬ x s . Каждую формулу, заданную в КНФ,можно изобразить словом из Λ∗1 , как обсуждалось в примере ..Предикат, принимающий значение 1 на тех и только тех словах изΛ∗1 , которые являются кодами КНФ выполнимых формул, назовем Sat(от английского слова satisfiability, одно из значений которого — выполнимость).Теорему Кука мы приводим без доказательства  :Теорема Кука.

Предикат Sat является NP-полным.Если показано, что некоторый предикат u является NP-полным,и при этом для некоторого другого предиката v ∈ NP установлено,что u ¶ p v, то из этого, очевидно, следует, что v тоже NP-полный.Пример .. Прямым следствием теоремы Кука является то, чторассмотренный в примере . предикат выполнимости произвольной, не обязательно заданной в КНФ, формулы является NP-полным.Полиномиальная сводимость предиката Sat к этому предикату очевидна: в качестве функции f , фигурирующей в определении .,можно взять функцию, которая преобразует слово x из Λ∗1 в скобку«)» или еще в какой-нибудь символ, не являющийся кодом какой-либо булевой формулы, всякий раз, когда слово x не является кодомкакой-либо КНФ, и преобразует x в x в противном случае (можноописать принадлежащий P алгоритм вычисления f (x)).Когда говорят о принадлежащих классам P и NP задачах распознавания и о NP-полных задачах, а не о предикатах и языках, то приэтом предполагают, что способ кодирования входных данных ясен изМы опускаем доказательство этой теоремы, называемой в некоторых источникахтакже теоремой Кука—Левина, из-за того, что оно требует привлечения специфической техники доказательств утверждений о машинах Тьюринга; такого рода доказательства выглядят естественно в определенном контексте, который отличается от контекста этого курса.

Отчасти это послужило и причиной того, что в §  мы оставили бездоказательства теорему Фишера—Рабина. Доказательство теоремы Кука имеется, например, в [], [], []. Прозрачное изложение идей доказательства принадлежностиклассу NP предиката, распознающего выполнимость произвольной булевой формулы,и полиномиальной сводимости такого предиката к Sat можно найти в [].Глава . Сводимостьконтекста и определен, по крайней мере, с точностью до полиномиальной сводимости. Обсуждая в дальнейшем задачи из примеровпредыдущего параграфа, мы будем иметь в виду рассмотренные тамспособы кодирования.Пример .. Покажем сводимость задачи выполнимости КНФк задаче о клике с указанным числом вершин (пример .).

ПустьКНФ F имеет вид (.). Построим граф G F с k1 + k2 + ... + k m вершинами, для которых используем обозначенияlij ,i = 1, 2, ..., m,j = 1, 2, ..., k i ,при этом вершины lij и lvw соединяем ребром, если и только есливыполнены два условия:• i 6= v,• конкретные литералы, скрывающиеся в (.) за обозначениямиlij и lvw , не являются отрицанием друг друга (скажем, если lij — это¬ x1 , а lvw — это x1 , то эти две вершины ребром не соединяются).Построение матрицы смежности графа G F может быть выполнено заполиномиально ограниченное время.Из определения клики и способа построения графа G F следует,что клика из m вершин в этом графе существует, если и только еслиформула (.) выполнима.

В самом деле, при наличии такой кликиполагаем x s = 0, когда литерал ¬ x s соответствует одной из вершинклики, а в остальных случаях x s = 1. В результате каждое Di в (.)равно 1.Наоборот, если заданная формула (.) выполнима, то при соответствующих значениях всех переменных x1 , x2 , ..., xn для каждогоi ¶ m можно выбрать j такое, что lij — это литерал со значением 1.Сделав такой выбор, мы получаем набор вершин, образующий кликус m вершинами.Если исходная КНФ имеет вид(¬ x1 ∨ ¬ x2 ) ∧ (x2 ) ∧ (x1 ∨ x2 ),то мы получаем граф G F с пятью вершинами (рис.

), в которомобнаруживается клика (l11 , l21 , l32 ) с тремя вершинами. Это соответствует тому, что исходная формула принимает значение 1 при x1 = 0,x2 = 1.Задача распознавания существования в графе клики с заданнымчислом вершин является NP-полной.§ .

Полиномиальная сводимость. NP-полные задачиl21а)l31l11l21б)l12l32l31l12l11l32Рис. . Построение графа G F для F = (¬ x1 ∨ ¬ x2 ) ∧ (x2 ) ∧ (x1 ∨ x2 ): а) выборвершин, б) проведение ребер.Доказано также, что задача распознавания гамильтоновости графаявляется NP-полной  . Упомянем еще одну очень известную NP-полную задачу, называемую задачей о рюкзаке. Задано конечное множество U, размер s(u) ∈ N+ и стоимость v(u) ∈ N+ каждого u ∈PU, а такжеa, b ∈ N+ . Существует ли такое подмножество U ′ ⊂ U, чтоs(u) ¶ a,Pu∈U ′v(u) ¾ b?u∈U ′?Из теоремы Кука следует, что для решения проблемы P = NP достаточно со всей тщательностью рассмотреть какой-нибудь один NP-полный предикат, например, тот же предикат Sat, и ответить на вопросо его принадлежности классу P.

Если он принадлежит классу P, тоP = NP в силу NP-полноты рассматриваемого предиката, если не принадлежит, то P 6= NP, так как найден предикат, принадлежащий NPи не принадлежащий P. Но этот заманчивый план до сих пор реализовать не удалось, усилия многих исследователей не привели к решению этой проблемы, хотя и устоялось мнение, что, скорее всего,P 6= NP. Это предположение влечет за собой рекомендацию: если доказано, что решаемая практическая задача (при надлежащей формализации в виде предиката на словах в алфавите) является NP-полной, тобыло бы опрометчивостью рассчитывать на нахождение в короткиесроки полиномиального алгоритма ее решения, и лучше попробоватьрешить эту задачу приближенно.Многие задачи фактического построения некоторого математического объекта вписываются в следующую схему: дано x; если существует y такое, что x вместе с y удовлетворяют фиксированному условию R(x, y), то найти такое y.

Соответствующая задача расОгромное число примеров NP-полных задач собрано в [].Глава . Сводимостьпознавания выглядит так: дано x; требуется определить, существуетли y такое, что x вместе с y удовлетворяют фиксированному условиюR(x, y). Мы полагаем, что x и y — это коды некоторых математических объектов, т. е. слова в некотором алфавите Λ.Пусть задача распознавания связана указанным образом с задачейпостроения, пусть R(x, y) ∈ P и полином p таков, что если существует какое-то решение задачи построения, то существует и такое решение y, что | y | ¶ p(| x |). Тогда задача распознавания принадлежит NPв соответствии с определением ., причем в качестве сертификатадля x выступает это решение y.В примерах из §  по рассмотренным задачам распознавания легко восстанавливаются соответствующие им задачи построения (построить набор логических значений переменных; построить делительданного числа; построить клику в графе, имеющую определенное количество вершин, и т.

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

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