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

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

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

Алгоритмы проверки выполнимости,основанные на переборе всех возможных комбинаций значений переменных x1 , x2 , ..., xn , не являются полиномиальными.Рассмотренный пример дает мотивацию определения . и проясняет смысл понятия «сертификат». Отметим два важных момента.) Перебор всех возможных слов y, | y | ¶ p(| x |), для проверкиравенства u(x) = 1 с помощью (.) может потребовать рассмотрения экспоненциального по отношению к | x | числа возможностей. Ноопределение . требует лишь, чтобы при u(x) = 1 сертификат существовал, вопрос же о сложности его построения не затрагивается.) Если u ∈ NP, то равенство u(x) = 0 означает, что соответствующего сертификата для слова y не существует. Другими словами,принадлежность x множеству истинности предиката подтверждаетсясертификатом, а непринадлежность — отсутствием сертификата.

По-Глава . Сводимостьэтому возможные значения 1 и 0 не являются симметричными илиравноправными; как показано в примере ., предикат, распознающий выполнимость булевой формулы, принадлежит NP, но мы неможем на основе только этого утверждать, что и предикат, распознающий невыполнимость булевой формулы, принадлежит NP (какоеслово могло бы быть сертификатом невыполнимой формулы?).Предложение .. P ⊆ NP.Доказательство. Определим R(x, y) = u(x) в (.) при любом слове y и будем считать пустое слово сертификатом любого x такого,что u(x) = 1; в качестве полинома p берем нулевой полином.Продолжим рассмотрение примеров.Пример ..

Согласно результатам Агравала, Кайала и Саксены(пример .), классу P принадлежит предикат, определенный на словах в алфавите {0, 1} и принимающий значение 1, если и только еслислово является записью простого числа. Рассмотрим близкую задачу.Для заданных 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).

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

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