Диссертация (1137435), страница 3
Текст из файла (страница 3)
Более формально, задача разрешения Π состоитпросто из двух множеств: множества Π всех возможных индивидуальныхзадач (instances, в дальнейшем в формулировках задач, называемых длякраткости входами) и множества индивидуальных задач Π ⊂ Π с ответом “да” (yes-instances). Стандартная форма для описания задач состоит издвух частей.
В первой части дается описание условия задачи, а во второй19части в терминах условия формулируется вопрос, предполагающий одиниз двух ответов - да или нет. Следуя традиции, мы будем писать словаУСЛОВИЕ и ВОПРОС строчными буквами.Индивидуальная задача принадлежит Π в том и только том случае,когда она может быть получена из стандартной формы описания подстановкой конкретных значений во все компоненты условия. Индивидуальнаязадача принадлежит Π в том и только том случае, когда ответом на вопросзадачи будет “да”.
Задачи разрешения могут быть формально представлены в виде языков. Для любого конечного множества символов Σ через Σ*обозначается множество всех конечных цепочек (слов), составленных изсимволов алфавита Σ. Произвольное подмножество ⊆ Σ* называетсяязыком в алфавите Σ.Соответствие между задачами разрешения и языками устанавливается с помощью схем кодирования (encoding schemes). Для данной задачиΠ, схема кодирования описывает каждую индивидуальную задачу из Πподходящим словом в некотором фиксированном алфавите Σ. Таким образом, задача Π и ее схема кодирования разбивают множество Σ* на трикласса: слова, не являющиеся кодами индивидуальных задач из Π, слова,являющиеся кодами индивидуальных задач из Π с ответом “нет"на вопроси слова, являющиеся кодами индивидуальных задач из Π с ответом “да".Третий класс слов и есть язык [Π, ], ставящийся в соответствие задачеΠ при кодировании .
С каждой задачей разрешения связана не зависящая от схемы кодирования формальная мера длины (размера) входа (inputlength). Она определяется как функция Length: Π → Z+ , которая прилюбой “разумной схеме кодирования” (подразумевающей “естественную20краткость” или экспоненциальную несжимаемость и “декодируемость”, обсуждение этих понятий можно найти в [8]) полиномиально эквивалентнадлине кода индивидуальной задачи, т.е.
существуют два полинома и ′такие, что если есть индивидуальная задача из Π и слово есть код при кодировании , то Length[] ≤ (||) и || ≤ ′ (ℎ[]), где || длина слова .Время работы алгоритма (программы для детерминированной машины Тьюринга или ДМТ-программы) решения индивидуальной задачи ∈ Π с размером входа определяется как число шагов до моментаостановки программы.
Временная сложность алгоритма для решения задачи Π определяется как максимальное время работы алгоритма средивсех индивидуальных задач со входом размера . Временную сложностьалгоритма будем обозначать как функцию (). Алгоритм называетсяполиномиальной ДМТ-программой, если существует такой полином , чтодля всех ∈ N () ≤ ().Класс полиномиально вычислимых функций P определяется как множество языков: = {: существует полиномиальная ДМТ-программа для которой = }.Для определения классов NP и #P, которые мы будем использоватьв дальнейшем, используется понятие недетерминированной машины Тьюринга (НДМТ), которая состоит из двух модулей: обычной ДМТ и модуляугадывания. Вычисление на НДМТ состоит из двух стадий - стадии угадывания и стадии проверки:1) на стадии угадывания, при получении индивидуальной задачи ,21происходит угадывание некоторой структуры(слова) ∈ Σ* ;2) и подаются на вход ДМТ на стадии проверки, которая выполняется как обычная программа ДМТ и либо заканчивается ответом “да”(если есть решение задачи ) либо ответом “нет”, либо продолжается безостановки.
Слово также называют свидетелем.Недетерминированный алгоритм (НДА) определяется как пара⟨угадай некоторое слово ; проверь детерминированным алгоритмом ⟩.НДА “решает"задачу разрешения Π, если следующие два свойства имеютместо для всех индивидуальных задач ∈ Π :1) Если ∈ Π , то существует такая структура , угадывание которойдля входа приведет к тому, что стадия проверки, начиная работу на входе(, ) закончится ответом “да".2) Если ̸∈ Π , то не существует такой структуры , угадываниекоторой для входа обеспечило бы окончание стадии на входе (, ) сответом “да”.Недетерминированный алгоритм, решающий задачу разрешения Πработает в течение “полиномиального времени”, если найдется полином такой, что для любой индивидуальной задачи Π ∈ Π найдется догадка, приводящая на стадии детерминированной проверки на входе (, ) кответу “да"за время (Length ||).Неформально, класс NP – это класс всех задач разрешения Π, которые при разумном кодировании могут быть решены недетерминированными алгоритмами за полиномиальное время или, другими словами, –это класс задач, для которых существует полиномиальное решение (свидетель), которое может быть проверено за полиномиальное время.22Полиномиальная сводимость (по Карпу) задачи разрешения Π1 к задаче разрешения Π2 (обозначается Π1 ∝ Π2 ) означает наличие функции : Π1 → Π2 , удовлетворяющая следующим двум условиям:1.
Существует полиномиальная ДМТ-программа, вычисляющая ;2. Для всех ∈ Π1 выполнение ∈ Π1 имеет место тогда и толькотогда, когда () ∈ Π2 .Полиномиальная эквивалентность задачи разрешения Π1 и задачиразрешения Π2 имеет место, когда Π1 ∝ Π2 и Π2 ∝ Π1 .Задача разрешения Π называется NP-трудной, если к ней полиномиально сводятся все задачи разрешения из класса NP. Задача разрешенияназывается NP-полной, если она лежит в классе NP и является NP-трудной.Неформально, NP-полная задача - эта самая (неединственная) трудоемкаязадача в классе NP. Классическим справочником по NP-полным задачамявляется книга [55] (см. русский перевод [8]), а также продолжающаясясерия статей “The ongoing guide of NP-complete problems”, которую ведетД.
Джонсон в Journal of Algorithms. В дальнейшем изложении нам понадобятся следующие полезные свойства (см. [8]), выполняющиеся для произвольных задач разрешения Π1 , Π2 , Π3 :1. Если Π1 ∝ Π2 , то Π2 ∈ влечет Π1 ∈ .2. Если Π1 ∝ Π2 и Π2 ∝ Π3 , то Π1 ∝ Π3 .3.
Если Π1 и Π2 принадлежат NP, Π1 NP-полна и Π1 ∝ Π2 , то Π2NP-полна.Класс coNP определяется как класс дополнений языков из NP. Формальное определение: язык принадлежит классу coNP, если существуетДМТ (, ) и полином такие, что = { | ∀, || ≤ () (, ) = 0}23(отметим, что в последним определении можно заменить (, ) = 0 на (, ) = 1).
Полные в классе coNP задачи определяются аналогично полным в классе NP задачам. Каждая coNP-полная задача является дополнением NP-полной задачи (и наоборот). Примером coNP-полной задачи может служить задача разрешения – является ли данная булева формула(заданная в дизъюнктивной нормальной форме) тавтологией.Теперь от задач разрешения мы перейдем к задачам подсчета, т.е.таких, в которых поднимается вопрос “каково число...?”. Ответы на подобные вопросы важны для правильной организации вычислительных ресурсов, особенно в случае, когда число объектов, порождаемых алгоритмом,велико, например, экспоненциально от входа.Задача поиска (search problem) Π состоит из множества Π конечныхобъектов, называемых индивидуальными задачами и, для каждой индивидуальной задачи Π ∈ Π , соответствующего (возможно пустого) множества Π [] конечных объектов, называемых решениями .
Алгоритм решает задачу поиска Π, если, получив на входе произвольную индивидуальнуюзадачу Π ∈ Π , он либо отвечает “нет"всякий раз, когда множество Π []пусто, либо выдает некоторое решение ∈ Π [].Заметим, что произвольная задача разрешения может быть сформулирована как задача поиска (интуитивно понятно, что получить решение задачи труднее, чем установить его существование), если положитьΠ [] = {“”}, если Π ∈ Π , и [] = ∅, в противном случае (т.е. еслиΠ ̸∈ Π ).Задача подсчета, основанная на задаче поиска Π, формулируется следующим образом: “дана индивидуальная задача , какова мощность мно-24жества Π (), т.е. сколько решений оно содержит?”. Мы будем записыватьзадачу подсчета следующим образом:ВХОД (INPUT) .ВЫХОД (OUTPUT) |Π ()|.Задача подсчета принадлежит классу #P, если существует недетерминированный алгоритм, такой что для каждой индивидуальной задачи Π ∈ Π число различных “догадок”, приводящих к принятию , естьв точности |Π ()|, а длина самого длинного принимающего вычисления(проверки, выдающей на выходе “да”) ограничена сверху полиномом от величины Length[].
Класс #P может быть определен в терминах СчитающихМашин Тьюринга, как это было сделано в работе [95].Считающая машина Тьюринга, СМТ (Counting Turing Machine), естьНДМТ с дополнительной лентой выхода, на которой особая головка пишет в двоичной записи число принимающих вычислений, соответствующихданному входу. СМТ имеет сложность () в худшем случае, если самоедлительное принимающее вычисление (на обычной НДМТ) для входа размера осуществляется за () операций.#P есть класс функций, которые могут быть вычислены считающимимашинами Тьюринга с полиномиальной сложностью.
В классе#P, такжекак и в классе NP, имеются полные задачи, но сводимость в классе #Pопределяется несколько иначе.Полиномиальная сводимость по Тьюрингу задачи поиска 1 к задачепоиска 2 (обозначается 1 ∝ 2 ) означает существование алгоритма ,который решает 1 , используя в качестве “подпрограммы” алгоритм длярешения задачи 2 , так что если был бы полиномиальным алгоритмом25решения 2 , то был бы полиномиальным алгоритмом для решения задачи 1 . Очевидно, что сводимость по Карпу является частным случаемсводимости по Тьюрингу, тем не менее справедливость обратного утверждения неизвестна.Задача подсчета 1 называется #P-полной если 1 ∈ #P и для всех2 ∈#P, 2 ∝ 1 .Задачи подсчета, соответствующие NP-полным задачам разрешения,#P-полны, однако множество задач подсчета, соответствующих полиномиальным задачам разрешения, также #P-полны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
