С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 41
Текст из файла (страница 41)
Отчасти это послужило и причиной того, что в § мы оставили бездоказательства теорему Фишера—Рабина. Доказательство теоремы Кука имеется, например, в [], [], []. Прозрачное изложение идей доказательства принадлежностиклассу 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б)l12l32l31l12l11l32Рис.
. Построение графа 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.В примерах из § по рассмотренным задачам распознавания легко восстанавливаются соответствующие им задачи построения (построить набор логических значений переменных; построить делительданного числа; построить клику в графе, имеющую определенное количество вершин, и т.
д.). Для доказательства принадлежности классу NP задачи распознавания мы брали в качестве сертификата саморешение соответствующей вычислительной задачи.Такой выбор сертификатов в ряде доказательств, видимо, и служитпричиной довольно распространенного представления, что класс Pобразуют вычислительные задачи, решаемые за полиномиально ограниченное время, а класс NP — вычислительные задачи, для каждой изкоторых за полиномиально ограниченное время можно проверить,является ли данное слово y ее решением. На самом деле, конечно,в классы P и NP входят только задачи распознавания, но упомянутое представление, будучи, строго говоря, неправильным, в известной мере согласуется с реальным положением вещей.Быстрый алгоритм распознавания наличия какого-то математического объекта, кодируемого словом из Λ∗ , может в некоторых случаях позволить быстро решать и задачу фактического построения этогообъекта.
Проиллюстрируем это примером.Пример .. Мы знаем, что задача распознавания простоты натурального числа n принадлежит классу P, — алгоритм Агравала, Кайала и Саксены (пример .) имеет битовую сложность O(m11 ), гдеm — битовая длина n. Вопрос о существовании полиномиального алгоритма факторизации (разложения на простые множители) остаетсябез ответа до сих пор при том, что алгоритмы факторизации имеютогромную важность, например, для криптографии.
Вернемся в связис этим вопросом к принадлежащей NP задаче, рассмотренной в примере .: для заданных n, k ∈ N+ , k < n, выяснить, имеется ли у числа n делитель l такой, что 1 < l ¶ k. Полиномиальный алгоритм реше-Задачиния этой задачи тоже неизвестен, но можно показать, что открытиетакого алгоритма — назовем его A — автоматически дало бы полиномиальный алгоритм факторизации (кстати сказать, существование Aавтоматически следовало бы из равенства P = NP, если бы оно вдругбыло доказано). Для этого можно воспользоваться бинарным поиском.Пусть уже установлено, что n не имеет делителей, меньших n1 ,где n1 < n, и пусть n2 таково, что n1 < n2 < n, и мы интересуемся наименьшим принадлежащим отрезку [n1 , nl2 ] простыммножителем чисmn +n2, мы сузим диапазонла n.
Тогда, применяя A к n, n3 , где n3 = 12поиска примерно вдвое: в зависимости от результата применения Aмы перейдем от отрезка [n1 , n2 ] либо к отрезку [n1 , n3 ], либо к отрезку [n3 + 1, n2 ]. Первоначально же полагаем n1 = 2, n2 = n. Применивалгоритм A не более m = ⌈log2 (n + 1)⌉ раз, мы найдем наименьшийпростой множитель t числа n.
Повторяем те же вычисления дляn′ =nt(.)и т. д. Общее число простых множителей числа n с учетом их кратности ограничено сверху величиной log2 n, и, значит, величиной m.Битовые затраты каждого деления (.) не превосходят Cm2 , гдеC — некоторая константа. Если битовая сложность алгоритма A естьO(md ), то сложность описанного алгоритма факторизации будет допускать оценку O(md+2 ), т. е.
этот алгоритм будет полиномиальным.Задачи. Задача умножения квадратных булевых матриц линейносводится к задаче построения транзитивно-рефлексивного замыкания (предполагается, что для сложностей рассматриваемых алгоритмов построения транзитивно-рефлексивного замыкания выполненоT(3n) = O(T(n))).Указание. Пусть M1 и M2 — две булевы матрицы порядка n. Пусть X — булева матрица порядка 3n:0 M100M2 .00 00Чему равны X 2 , X 3 ? Воспользоваться формулой (.) для транзитивно-рефлексивного замыкания.Глава . Сводимость.
Здесь речь идет о линейной сводимости P ¶ Q задач, связанных с мультипликативными операциями над квадратными числовыми матрицами порядка n. Рассматриваются лишь такие алгоритмырешения задачи Q, для сложности по числу арифметических операций каждого из которых выполняется соотношение T(kn) = O(T(n)),k = 2, 3.Требуется показать, что задача умножения произвольных квадратных матриц линейно сводится к задачеа) умножения симметричных квадратных матриц;б) умножения верхних треугольных матриц;в) обращения невырожденных матриц.Указание.
Так же, как в предыдущей задаче, здесь можно прибегнутьк матрицам размера, большего n, используя исходные матрицы как блокидля построения новых матриц. В пункте в) полезно предварительно установить вид матрицы− 1In M 10In M 2 ,000Inгде M1 , M2 — исходные матрицы, In — единичная матрица порядка n.. а) Доказать свойство (R) рациональных функций, сформулированное в § .Указание. Достаточно доказать, что если полином p(x1 , x2 , ..., xn ) тождественно равен нулю на некотором непустом открытом множестве U ⊂ Rn , тоэтот полином нулевой.
При n = 1 утверждение очевидно. Пусть n > 1 и точка v = (v1 , v2 , ..., vn ) ∈ Rn такова, что p(v1 , v2 , ..., vn ) 6= 0. Пусть u ∈ U . Множество U — открытое, поэтому у точки u существует окрестность некоторогорадиуса r > 0, целиком принадлежащая U . Пусть l — расстояние от u до v ,а c1 , c2 , ..., cn — координаты вектора единичной длины, направленного из uв v . Если t пробегает множество R, то формулыx1 = u1 + c1 t,x2 = u2 + c2 t, ...,x n = un + cn t(.)задают прямую в Rn , причем при t = 0 получается точка u, а при t = l — точка v .
Остается рассмотреть для полинома p̄(t) одной переменной t , получающегося подстановкой (.) в p(x1 , x2 , ..., xn ), его значения в точке t = l и наинтервале −r < t < r .б) Для каких целых n ¾ 1 справедливо утверждение, что если произвольный полином с вещественными коэффициентами отx1 , x2 , ..., xn обращается в нуль на бесконечном подмножестве множества Rn , то этот полином является нулевым?.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
