ПОИСК Статьи Рисунки Таблицы Вероятностные алгоритмы и класс ВРР. Проверка простоты чиИерархия сложностных классов из "Классические и квантовые вычисления" Класс NP определён только для предикатов. Говорят, например, что свойство графа иметь гамильтонов цикл принадлежит NP . [c.29] Гамильтоноб цикл — замкнутый путь в графе, проходящий через все вершины графа ровно по одному разу. Граф, в котором есть хотя бы один гамильтонов цикл, называется гамилътоноьъш. [c.29] Путь вычисления НМТ определяется выбором одного из возможных переходов на каждом такте работы. Недетерминпрованность приводит к тому, что путей вычисления для НМТ, работающей на данном входном слове, оказывается много. [c.30] Замечание 2.1. Приведенные варнанты определения эквивалентны. Чтобы исключить возможность ответов да на длинных путях вычисления, достаточно взять ПМТ, имитирующую исходную ПМТ и подсчитывающую количество сделанных исходной ПМТ шагов. Когда число шагов превышает р( ж ), машина останавливается. [c.30] Замечание 2.2. В предыдущем рассуждении допущена одна тонкая ошибка. В онределенин ничего не сказано о полиноме р(н), кроме факта его существования. Если коэффициенты полинома невычислимы, могут возникнуть проблемы с указанным выше способом сведения одного определения к другому (нужно вычислить значеппе полинома). Чтобы в дальнейшем избегать этой сложности, будем считать, что полином имеет целые коэффициенты. [c.30] Замечание 2.3. Пеносредственно из определения 2.1 следует, что Р С МР. Является ли это включение строгим Довольно интенсивные, хотя и безуспешные, попытки ответить на этот вопрос продолжаются уже почти 30 лет. Недавно С.Смейл включил проблему Р = МР в число трёх важнейших математических проблем следующего столетня (две другие — гипотеза Рнмапа и гипотеза Пуанкаре). [c.30] Пример 2.1. Пусть R x, у) = г/ есть гамильтонов цикл в графе ж . Более точно нужно сказать так ж есть двоичный код некоторого графа, SL у — код гамильтонова цикла в этом графе (используем такое коднрованне, при котором код цикла ие длиннее кода графа), такие что.. . . Возьмём q n) — п. Тогда Ь х) будет в точности означать, что в графе найдётся гамильтонов цикл. [c.31] Теорема 2.1. Определения 2.1 и 2.2 эквивалентны. [c.31] Доксюательство. Опр. 2.1 опр. 2.2. Пусть есть ПМТ М и полином р п) из первого определения. Рассмотрим предикат R x,y) = = у есть протокол работы М на возможном пути вычисления со входом X дающего ответ да за время, не превосходящее р( ж ) . Длина такого протокола при разумном кодировании линейно зависит от времени вычисления (если использовать в качестве протокола описанную в доказательстве теоремы 1.2 таблицу вычисления, то квадратично), поэтому в качестве q n) для второго определения можно взять р п) р п)), умноженный на подходящую константу. [c.31] Чтобы закончить доказательство в этом случае, осталось проверить, что Л(, ) е Р. Это почти очевидно. Мы должны проверить протокол некоторой ПМТ, работающей за полиномиальное время. -Это займёт нас примерно на то же время (совершенно незачем смотреть на одну ячейку экспоненциально долго). [c.31] Пусть есть R, q из определения 2.2. Построим М для определения 2.1. Она работает в два этапа. [c.31] Вначале М недетерминированно пишет у (который в силу определения 2.2 существует для любого слова х, для которого L x) = 1). Говорят ещё, что М отгадывает ( guesses ) у. Более точно это означает, что М находит правый конец входного слова, сдвигается ещё на одну ячейку вправо, записывает в неё ещё раз сдвигается вправо и переходит в такое недетерминированное состояние, в котором она пишет один из символов на ленту, сдвигается вправо и выбирает между сохранением этого состояния и переходом в (уже детерминированное) состояние начала следующего этапа. [c.31] Ещё одно определение класса NP есть не более чем вариант определения 2.2, но именно в такой форме его удобно обобщать и получать определения других сложностных классов. [c.32] Поэтому они действуют следующим образом. А и М оба смотрят на слово X, после чего М сообщает некоторую информацию (слово у), которая должна убедить А, что Ь х) = 1. Используя эту информацию, А проверяет убедительность аргументов М некоторым полиномиальным способом. [c.32] Эквивалентность этого определения онределению 2.2 ие вызывает сомнений. Действительно, из-за полиномиальной ограниченности короля А, сообщение волшебника М должно иметь полиномиальный размер. В остальном различия между определениями чисто внешние. [c.32] Пункт б) следует из пункта а). [c.33] Определение 2.5. Предикат Ь NP называется NP-rio, гньгж, если любой предикат из NP к нему сводится. [c.33] Если некоторый NP-пoлный предикат можно вычислять за время Т п), то любой предикат пз NP можно вычислять за время Т(п ) для некоторого фиксированного числа с. Такая потеря эффективности считается в этой науке несущественной. [c.33] Теорема 2.2 (Кук, Левин). 1) SAT NP 2) SAT — -полна. [c.33] Вернуться к основной статье