С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 40

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

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

Рассмотрим близкую задачу.Для заданных n, k ∈ N+ , k < n, выяснить, имеется ли у числа n делитель l такой, что 1 < l ¶ k. Числа n и k задаются в двоичной системе;используя разделитель «;», мы можем кодировать пару n, k словомв алфавитеΛ2 = {0, 1, ; }.Если слово x кодирует указанным образом пару n, k, то в качествесертификата можно взять двоичную запись некоторого конкретногоделителя l, 1 < l < k. Тогда входящий в (.) предикат R(x, y) долженпринимать значение 1, если и только если(a) x является кодом пары n, k, удовлетворяющей сформулированным выше условиям,(b) y является двоичной записью некоторого числа l такого, чтоl ¶ k и при этом l | k.Существует алгоритм проверки условий (a), (b), вычислительные затраты которого ограничены величиной C(| x | + | y |)2 , где C — некоторая константа. Можно в (.) положить p(n) = n, так как l ¶ k. Этоговорит о том, что рассматриваемый предикат на Λ∗2 принадлежитклассу NP.

Неизвестно, принадлежит ли он также классу P.Пример .. В связи с изучением классов P и NP рассматривается большое число задач на графах, при этом графы, как правило,задаются матрицами смежности. В алфавите Λ2 матрица смежности§ . Существование задач распознавания, не принадлежащих Pкодируется словом, в котором строки матрицы выписаны одна за другой через разделитель «;». Легко видеть, что классу NP принадлежитпредикат, принимающий значение 1, если и только если слово является кодом графа, обладающего гамильтоновым циклом, т.

е. циклом, проходящим по одному разу через все вершины графа (рис. );а)б)Рис. . а) Гамильтонов цикл; б) граф без гамильтонова цикла.сертификатом может, например, являться последовательность двоичных номеров вершин гамильтонова цикла. Эти номера выписываютсяв одно слово через разделитель «;».Аналогичным образом, классу NP принадлежит предикат, принимающий значение 1, если и только если слово является кодом графа,обладающего кликой с заданным числом m вершин. При этом кликой называется набор m вершин, любые две из которых соединеныребром (в изображенном на рис. а графе имеется несколько кликс тремя вершинами, но нет ни одной с четырьмя вершинами).

Исходные данные кодируются словом в алфавите Λ2 : сначала идет матрицасмежности, записанная так, как было сказано выше, затем, после разделителя «;», — число m в двоичной системе. Эта задача принадлежитклассу NP, сертификатом может быть слово, составленное из двоичных номеров вершин клики, перечисленных через разделитель «;».Относительно обоих этих предикатов на Λ∗2 неизвестно, принадлежат ли они классу P.§ .

Существование задач распознавания, не принадлежащих P.Связь моделей МТ и РАМВозникает вопрос, существуют ли вообще задачи распознавания принадлежности слов некоторому языку, разрешимые алгоритмически,но не принадлежащие P. Один из первых примеров задачи такого рода в  г. был обнаружен М. Фишером и М. Рабином. Этот примерсвязан с так называемой арифметикой Пресбургера. Рассматривают-Глава . Сводимосться логические формулы, записанные с соблюдением обычных синтаксических правил с помощью некоторого числа переменных, знаков +, =, логических связок ∨, ∧, ¬ и скобок; при этом каждая переменная должна быть связана одним из кванторов ∀, ∃, а множествомзначений переменных является N.

Каждая такая формула, трактуемаякак утверждение о неотрицательных целых числах, имеет значение«истина» или «ложь» (1 или 0). Арифметика Пресбургера — это совокупность всех истинных формул указанного вида. Так, формулы∀ x ∃ y (x + y = x),∀ x ∀ y (x + y = y + x) ∧ ¬(∀ x ∃ y (x + y = y))принадлежат арифметике Пресбургера, а формула ∀ x ∃ y (x + y = y) —нет. Как и ранее, мы будем использовать переменные, имеющие видбуквы x, за которой следует некоторое двоичное число (номер переменной). В алфавитеΛ3 = {x, 0, 1, +, =, ∨, ∧, ¬, ∀, ∃, (, )}формула ∀ x ∃ y (x + y = x) запишется в виде ∀ x1∃ x10(x1 + x10 = x1)и т. д.

М. Пресбургером было в  г. доказано существование алгоритма, который дает ответ на вопрос, является ли данное слово в алфавите Λ3 формулой арифметики Пресбургера (разумеется, основнаязадача, решаемая этим алгоритмом, состоит в различении синтаксически правильных формул, принимающих значение 1 и соответственно 0; слова, не являющиеся синтаксически правильными формулами,легко распознаются и отвергаются).Теорема, доказанная в  г. Фишером и Рабином, может бытьсформулирована так (мы не приводим доказательства  ).Теорема Фишера—Рабина. Существует константа c > 0 такая,что для любого алгоритма A, распознающего среди всех слов из Λ∗3 те,которые являются формулами арифметики Пресбургера, существуетцелое n0 такое, что для любого n > n0 найдется слово из Λ∗3 длины n,cnдля работы с которым алгоритму A потребуется более 22 вычислительных шагов.Из теоремы Фишера—Рабина следует, что арифметика Пресбургера как предикат на Λ∗3 не принадлежит классу P.В доказательстве теоремы Фишера—Рабина вычислительные шагисоответствуют рассмотрению MT в качестве модели вычислений.С помощью модели МТ доказывается, например, и теорема о том,что если t(n) — вычислимая с помощью некоторой машины ТьюрингаСм.

[].§ . Существование задач распознавания, не принадлежащих Pфункция натурального аргумента, принимающая натуральные значения, то существует такой язык в некотором алфавите, что сложностьлюбого алгоритма (в виде машины Тьюринга) распознавания принадлежности слова этому языку будет больше t(n) для всех достаточнобольших n.  В определенном смысле эта теорема является более общей, чем теорема Фишера—Рабина, но она очень абстрактна. ТеоремаФишера—Рабина примечательна тем, что в ней идет речь о некоторомсодержательном в математическом смысле языке (предикате).Модель МТ, однако, выглядит избыточно затратной в сравнениис моделью РАМ в силу, например, того, что если некоторый символ хранится в ячейке a ленты и для определения хода дальнейшихвычислений надо сравнить этот символ с символом, расположеннымв ячейке b, которая находится далеко от ячейки a, то передвижениеголовки машины Тьюринга из a в b потребует большого числа тактов работы и, следовательно, больших затрат, а в случае модели РАМсверх самой операции сравнения здесь нет затрат вообще.Приведем соображение, которое можно оформить в виде теоремы  , показывающее, что если некоторые вычисления имеют полиномиальную сложность при использовании РАМ, то они будут иметьполиномиальную сложность и при использовании МТ.

Для простоты будем считать, что речь идет о преобразовании слов в алфавитеΛ = {0, 1} и соответственно о битовой сложности вычислений. Будемтакже считать, что на каждое присваивание тратится некоторое учитываемое время, в том числе на присваивание вида a := b, при котором не выполняется никаких сравнений и изменений бит. Это даетвозможность предполагать, что для сложности T(n) по числу битовыхопераций произвольного алгоритма и его пространственной сложности S(n), измеряемой числом используемых дополнительных ячеек,в худшем случае выполняется соотношение S(n) ¶ C · T(n) при некоторой положительной константе C.Пусть f : Λ∗ → Λ и fPAM — некоторый алгоритм вычисления f с помощью РАМ, имеющий битовую сложность TfPAM (n), которая полиномиально ограничена по длине n = | x | входа x (считаем, что в каждой ячейке РАМ размещается 0 или 1).

Пусть 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-полных задачах, а не о предикатах и языках, то приэтом предполагают, что способ кодирования входных данных ясен изМы опускаем доказательство этой теоремы, называемой в некоторых источникахтакже теоремой Кука—Левина, из-за того, что оно требует привлечения специфической техники доказательств утверждений о машинах Тьюринга; такого рода доказательства выглядят естественно в определенном контексте, который отличается от контекста этого курса.

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

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