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

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

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

Если для решения важной задачи никак не удается найти алгоритм, сложностькоторого хотя бы при каком-нибудь показателе d допускала бы оценку O(nd ), то сам вопрос о существовании такого алгоритма нельзяназвать праздным.Иногда бывает очень трудно установить принадлежность или соответственно непринадлежность задачи классу P, состоящему из таких задач, для которых существует полиномиальный алгоритм решения. В классе P выделяют подкласс P тех вычислительных задач,где результатом может быть лишь 1 или 0, т.

е. фактически «да» или«нет», что типично для задач распознавания. К этим задачам относится, например, задача распознавания выполнимости булевой формулы, задача распознавания существования в графе гамильтонова цикла и т. д. Неизвестно, существуют ли полиномиальные алгоритмы ихрешения, но сравнительно легко устанавливается их принадлежностьспециальному классу NP. Определение класса NP будет дано ниже, изнего будет следовать, что P ⊂ NP. Если бы было доказано, что P = NP,то в широком спектре случаев мы бы легко устанавливали принадлежность задачи распознавания классу P, т. е. устанавливали бы существование полиномиального алгоритма распознавания; его разработка — это отдельный вопрос. Но равенство P = NP по сей день недоказано, и есть основания подозревать, что оно неверно.

Возникает?проблема P = NP, о которой мы тоже будем говорить.Вначале скажем о ряде ограничений, налагаемых на рассматриваемые задачи. Во-первых, речь будет идти о задачах распознавания техслов в данном алфавите Λ, которые принадлежат оговоренному подмножеству (языку) L множества всех слов Λ∗ в этом алфавите. Всеобъекты, о которых идет речь в рассматриваемых задачах, должныбыть представлены (закодированы) словами в алфавите Λ, входомалгоритма является одно-единственное слово в алфавите Λ. Размервхода x — это всегда длина | x | (число букв) в слове x. Вычислительные затраты должны учитываться достаточно тщательно, неучтеннойможет оставаться лишь незначительная часть операций (во всякомслучае, допускающая полиномиальную верхнюю оценку). Если имеется в виду модель вычислений РАМ, то предполагается, что вычисле-§ .

Классы P и NPния выполняются на базе конечного множества операций с тем илииным числом операндов, преобразующих буквы алфавита Λ в буквыалфавита Λ; исследуется сложность по числу этих операций — подобие битовой сложности. Требуется также учет числа присваиванийв ходе выполнения алгоритма.Таким образом, содержательная задача распознавания (например,задача существования пути с фиксированными свойствами в заданном графе) должна быть для обсуждения ее принадлежности классамP и NP переформулирована в виде задачи распознавания принадлежности заданного слова некоторому языку.

Такая формализация необходима потому что одна и та же математическая идея при одном издвух разных способов представления данных может приводить к полиномиальному алгоритму, а при другом — нет.?Часто при обсуждении проблемы P = NP исходят из машины Тьюринга (МТ) как модели вычислений, при этом вычислительные затраты измеряются числом тактов работы машины. Это связано с тем,что модель МТ удобнее модели РАМ при доказательстве разного рода теорем об алгоритмах, в особенности — теорем о невозможностиалгоритмов с теми или иными свойствами.

Но модель РАМ ближе,чем МТ, к реальным вычислительным устройствам, и хотелось бы,чтобы результаты исследования классов P и NP, проводимые на основе модели МТ, сохраняли свою значимость для модели РАМ. Ихзначимость действительно сохраняется, о чем будет сказано в концеэтого параграфа, а до той поры мы, как правило, не будем делатьуточнений относительно модели вычислений. Но, повторяем, операции преобразования букв, входящих в слова, должны подсчитыватьсятщательно.По сути дела, в каждой задаче распознавания принадлежностислова языку L обсуждается некоторый предикат u(x), областью определения которого является все множество Λ∗ , и u(x) = 1, если и только если x ∈ L. В дальнейшем нам часто будет удобно говорить нео языках, а о предикатах (по существу, это, конечно, одно и то же, нопредикаты несколько предпочтительнее из-за того, что к ним можноприменять логические операции, кванторы и т.

д.). Соответственно,мы будем говорить о принадлежности предиката классу P и т. д. Иногда нам будет удобно рассуждать о предикатах не одной, а несколькихтаких переменных, которые принимают значения в Λ∗ . В этих случаях без специального упоминания предполагается, что в алфавит Λвключены некоторые разделители: если, скажем, разделитель «запятая» (т. е. «,») включен в Λ, то v(x, y) имеет один аргумент x, y, гдеx и y суть слова в Λ∗ , не содержащие разделителя «,» (кавычки по-Глава .

Сводимостьставлены, чтобы не нарушать пунктуацию фразы). Соответственно,длиной пары слов x, y является | x | + | y | + 1.Теперь обсудим класс предикатов NP. Само его странное обозначение NP есть не что иное, как аббревиатура от английскихслов nondeterministic polynomial — недетерминированный полиномиальный. Изначальное определение класса NP, появившееся в теориисложности в начале -х годов XX столетия, опиралось на понятиенедетерминированного алгоритма  . Позднее появилось эквивалентное определение, не прибегающее к недетерминированности.Определение .. Заданный на Λ∗ предикат u(x) принадлежитклассу NP, если существуют предикат R(x, y) ∈ P и полином p(n) такие, что u(x) можно представить в видеu(x) = ∃ y ∈Λ∗ ,| y |¶ p(| x |) R(x, y).(.)В том случае, когда u(x) = 1, слово y называется сертификатом слова x.Пример .. Булева формула f (x1 , x2 , ..., xn ) выполнима, если существуют значения x10 , x20 , ..., xn0 ∈ {0, 1} переменных x1 , x2 , ..., xn такие, чтоf (x10 , x20 , ..., xn0 ) = 1;в противном случае булева формула невыполнима.

Так, булева формула¬(¬ x 1 ∨ x 2 )(.)выполнима, так как ее значение при x1 = 1, x2 = 0 равно 1, а булеваформула x1 ∧ ¬ x1 одной переменной x1 невыполнима, так как и приx1 = 1, и при x1 = 0 значение этой формулы есть 0.Любая булева формула может быть закодирована словом в алфавитеΛ1 = {x, 0, 1, (, ), ¬, ∧, ∨},для этого переменные x1 , x2 , x3 , ... кодируются как x1, x10, x11, ...:вслед за буквой x помещается номер переменной в двоичной системе. Формула (.) кодируется как ¬(¬ x1 ∨ x10), при этом, например,слово )x1x ¬ в алфавите Λ1 не является кодом какой-либо булевойформулы. Можно предложить простой алгоритм, который проверяет,является ли данное слово в алфавите Λ1 кодом какой-либо булевойформулы, а также алгоритм, который по данному коду некой булевой формулы и данным булевым значениям (нулям и единицам) техСм., например, [].§ .

Классы P и NPпеременных, которые фактически присутствуют в этой формуле, находит ее значение. На основе этих двух алгоритмов можно построитьалгоритм, который по данному слову x ∈ Λ∗1 и слову y, являющемуся конечной последовательностью нулей и единиц, проверяет, верноли, что(a) x является кодом некоторой булевой формулы,(b) значение закодированной словом x булевой формулы при техзначениях фактически присутствующих в ней переменных, которыепоследовательно указаны в слове y, равно 1.(Число нулей и единиц в слове y равно числу переменных, фактически присутствующих в закодированной булевой формуле: например, в булевой формуле x3 ∨ x15 фактически присутствуют две переменные, хотя для них и использованы большие индексы; сертификатом выполнимости этой формулы служит, например, слово 11.) Такой алгоритм можно сделать полиномиальным.

Это говорит о том,что при указанном способе кодирования булевых формул предикат,распознающий выполнимость булевой формулы, принадлежит классу NP, — сертификатом является слово y, указывающее значения переменных, при которых значение булевой формулы равно 1, а значение предиката R(x, y), входящего в (.), вычисляется с помощьюалгоритма, проверяющего (a) и (b).

Полином p(n) можно взять равным n, так как | y | ¶ | x | в силу того, что y содержит значения толькотех переменных, которые фактически присутствуют в булевой формуле.Неизвестно, принадлежит ли классу P предикат на словах из Λ∗1 ,распознающий выполнимость. Алгоритмы проверки выполнимости,основанные на переборе всех возможных комбинаций значений переменных 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, если и только еслислово является записью простого числа.

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

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