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

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

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

д.). Для доказательства принадлежности классу 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 M100M2  .00 00Чему равны X 2 , X 3 ? Воспользоваться формулой (.) для транзитивно-рефлексивного замыкания.Глава . Сводимость. Здесь речь идет о линейной сводимости P ¶ Q задач, связанных с мультипликативными операциями над квадратными числовыми матрицами порядка n. Рассматриваются лишь такие алгоритмырешения задачи Q, для сложности по числу арифметических операций каждого из которых выполняется соотношение T(kn) = O(T(n)),k = 2, 3.Требуется показать, что задача умножения произвольных квадратных матриц линейно сводится к задачеа) умножения симметричных квадратных матриц;б) умножения верхних треугольных матриц;в) обращения невырожденных матриц.Указание. Так же, как в предыдущей задаче, здесь можно прибегнутьк матрицам размера, большего n, используя исходные матрицы как блокидля построения новых матриц.

В пункте в) полезно предварительно установить вид матрицы− 1In M 10In 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 , то этот полином является нулевым?.

Функция f (n) = ⌈log2 n!⌉ является нижней границей сложности по числу сравнений алгоритмов сортировки массивов длины nЗадачипопарно различных рациональных чисел c помощью сравнений и четырех арифметических операций (в предложении . речь шла о сортировке вещественных чисел).. Функция f (n) = ⌈log2 (n + 1)⌉ является нижней границей сложности по числу сравнений алгоритмов поиска места элемента в упорядоченном массиве длины n попарно различных вещественных чисел c помощью сравнений и четырех арифметических операций..

Пусть известен алгоритм, который по данным c, m, c > 1,1(построитьm ∈ N+ , строит m значащих двоичных цифр числаcm значащих цифр некоторого числа x, 0 < x < 1, — это в данномконтексте означает отыскать первую ненулевую цифру после запятой в двоичной записи этого числа, а затем отбросить все цифрыпосле m цифр, отсчитанных от найденной), и пусть сложность этогоалгоритма есть O( f (m)), где f (m) — некоторая функция такая, что дополнительно известен алгоритм умножения произвольных a, b ∈ N+ ,сложность которого тоже есть O( f (m)), где m = max{λ(a), λ(b)}.

Наоснове этих двух алгоритмов сконструировать алгоритм построениячастного и остатка от деления положительных целых a и b, имеющийсложность O( f (m)), m = max{λ(a), λ(b)}.Указание. Нужно построить q и r такие, что a = qb + r , 0 ¶ r < b, или11a = q + s, 0 ¶ s < 1. Возникновение погрешности при вычисленииможетbbпривести к тому, что найденное q будет отличаться на 1 от точного значения; несколько добавочных проб помогут найти точные q и r , не изменяяоценки O( f (m)) для сложности.11. Пусть c > 0 и y0 удовлетворяет неравенствам¶ y0 ¶ ; пусть2ccпоследовательность y0 , y1 , y2 , ...

получена по рекуррентной формулеyi = 2 yi−1 − ci yi2−1 ,i = 1, 2, ...1Тогда последовательность y0 , y1 , ... сходится к .c. (Продолжение предыдущей задачи.) Пусть c ∈ N+ . Справедливо следующее утверждение  . Пусть y0 удовлетворяет неравенствам11¶ y0 ¶ и последовательность y0 , y1 , y2 , ... получена по рекуррент2ccной формулеyi = 2 ỹi−1 − ci ỹi2−1 ,См. [, разд. .].i = 1, 2, ...,(.)Глава . Сводимостьгде• целое ci таково, что λ(ci ) = λ(c), и если λ(c) > 2i , то первые 2i цифрчисла ci совпадают с соответствующими цифрами числа c, а последующие цифры суть нули, если же λ(c) ¶ 2i , то ci = c;• ỹ0 получается из y0 отбрасыванием всех цифр после первой значащей цифры;• после вычисления значения yi , i > 0, по рекуррентной формуле (.) в нем отбрасываются все цифры, идущие после первых 2i значащих цифр, — это дает значение ỹi .Тогда первые 2i − 3 значащие цифры числа yi совпадают с соответ1при i > 1.

Считая этот факт установствующими цифрами числаcленным и используя решение задачи , доказать, что задача деления одного целого числа на другое с остатком линейно сводитсяк задаче умножения двух целых чисел. (Размером входа считаетсяm = max{λ(a), λ(b)}, где a и b — исходные числа, при этом считаем,что m есть число вида 2k ; всюду подразумеваются битовые затраты;если это нужно, можно считать, что сложность f (m) умножения удовлетворяет условиям f (m) ¶ f (2m) ¶ 4 f (m)).Указание. Соответствующий алгоритм построения частного и остатка ужеописан в этой задаче и задаче . Достаточно доказать, что алгоритм приближенного обращения c, описанный в этой задаче, имеет сложность R(2k )такую, что R(2k ) ¶ γ f (2k ) для некоторой константы γ.

Подобрать γ так, чтобыдоказательство проводилось индукцией, и индуктивный переход был основанна неравенствеR(2k ) ¶ R(2k−1 ) + 2 f (2k−1 ) + δ2k−1 ,где константа δ определяется, в частности, тем, какой алгоритм сложениячисел используется.. Верно ли, что для доказательства того, что P = NP, достаточнопоказать, что хотя бы одна задача из NP принадлежит P?. Существуют ли в NP задачи, не являющиеся NP-полными?.

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

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