М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 49
Текст из файла (страница 49)
Упражнение 3.20 (теорема Эйлера). Докажите теорему Эйлера. Для случая, когда из каждой вершины выходит четное число ребер, дайте конструктивную процедуру нахождения эйлерова цикла. Эквивалентность задачи о существовании делителя и задачи о разложении на множители (задачи факторизации целого числа) является частным случаем одного из наиболее важных понятий в теории сложности, а именно понятия сводимоспги. Интуитивно мы понимаем, что некоторые задачи являются частными случаями других задач. Менее тривиальный пример сводимости — это сведение задачи НС к задаче коммивояжера (ТЯР— «ьгаче!1пб за1евшап ргоЪ|ешз). Задача коммивояжера состоит в слепующем: дано п городов 1, 2,..., п, расстояния между которыми (обозначим их г(; ) являются целыми неотрицательными числами. Для данного числа г( надо выяснить, существуег ли обход всех этих городов, общая длина которого меньше И.
Сведение задачи НС к задаче ТЯР осуществляется следующим образом. Пусть у нас есть граф с и вершинами. Будем считать, что каждая вершина— это город, что расстояние 4 между городами г и у' равно единице, если вершины г и у соединены, и двум, если они не соединены. Тогда любой обход этих городов, длина которого меньше п + 1, — это в точности гамильтонов цикл.
Следовательно, если у нас есть алгоритм для решения задачи ТЯР, мы можем переделать его в алгоритм для решения задачи НС без больших дополнительных затрат. Это и есть пример сводил«оспзи: мы свели задачу НС к задаче ТЯР. Сводимостью мы будем пользоваться на протяжении всей книги. Более общее понятие сводимости проиллюстрировано на рис. 3.11. Говорят, что язык В сеодигпся к языку А, если существует такая машина Тьюринга В, работающая полиномивльное время, что х б В тогда и только тогда, когда В(х) б А (здесь В(х) — результат применения машины В к слову х). Таким образом, если у нас имеется алгоритм, распознающий язык А, то за счет небольших дополнительных затрат мы можем распознать и язык В. В этом смысле язык В явлнется по существу не труднее языка А.
«Утверждение сформулировало неверно: количество ребер в графе может быть П(пз). Выполните зто упражнение, полагая, что и- ркзмер представления графа (скажем сумма числа вершин и ребер) При етом связность графа также проверяется за О(п) операций— Прши. ред. 3.2. Анализ вычислительных задач 193 Верно ли, что х Е В? Вычислите В(х) за полиномиальное время «Да» или «Нег» Ряс. 3.11, Сзодиыость языка В к языку А. Упражнение 3.21 (трвнзитивность сводимости).
Покажите, что если язьпс Ь| сводится к языку Ьз, а язык Ьз сводится к языку Ьз, то язык Ь| сводится к языку Ьз. В некоторых классах сложности есть задачи, являющиеся полными по отношению к этим классам; это означает, что в данном классе содержится язык Ь, являющийся в нем «наиболее трудным» для распознавания в том смысле, что любой другой язык в этом классе сводится к Ь. Не во всяком классе сложности существует полная задача, но многие вз тех классов, которые мы будем рассматрявать, этим свойством обладают. Тривиальный пример — класс Р.
Пусть Х вЂ” любой язык в классе Р, не являющийся пустым и не совпадающий с множеством всех слов (т. е. существует слово хз, не принадлежащее Ь, и слово хз, принадлежащее Ь). Тогда любой другой язык Ь' из класса Р можно свести к Ь, используя для данного слова х процедуру, работающую полиномиальное время, для того, чтобы выяснить, лежит ли х в Ь».
Вели нет, положить В(х) = хз, если да, положить В(х) = хз. Упражнение 3.22. Предположим, что язык Ь полон в некотором классе сложности и что»» — другой язык в том же классе, причем Ь сводится к Ь'. Покажите, что Г также полон в этом классе. Менее тривиальным обстоятельством является то, что класс ХР также содержит полные задачи. Важным примером такой задачи (и прототипом для всех остальных» 1Р-полных задач) является задача вмполнимоспзи схемы, сокращенно называемая СЯАТ: пусть дана булева схема, состоящая из элементов АХ1Э, 011 и НОТ; существуют ли значения входов, при которых на выходе получится 1, или, другими словами, выполнима ли схема на каком-нибудь входе? Утверждение о ХР-полноте задачи СЯАТ известно как теорема Куна-Левина; дщим набросок ее доказательства.
»Ъорема 3.2 (Кука — Левина). Задача СЯАТ является г(Р-полной. Доказательство состоит из двух частей. В первой части мы показываем, что задача СЯАТ принадлежит классу г?Р, а во второй — что любой язык класса 1«(Р можно свести к СЯАТ. Обе части доказательства основаны на технике 13 к««««««» «я« 194 Глава 3. Введение в информатику моделирования: в первой части мы по существу показываем, что машина Тьюринга может эффективно моделировать схему, а во второй — что схема может эффективно моделировать машину Тьюринга. Обе части доказательства проводятся довольно просто; для иллюстрации вторую часть мы излагаем более или менее подробно. Итак, в первой части доказательства покажем, что задача СЯАТ принадлежит Р1Р.
В самом деле, если дана схема из и элементов и потенциальное свидетельство выполнимости ш (набор значений входных переменных), то, очевидно, можно проверить на машине Тьюринга за полиномиальное время, выполнима ли схема на входе и, откуда и следует, что СЯАТ принадлежит ХР. Во второй части доказательства покажем, что любой язык Ь е г1Р можно свести к СЯАТ. Другими словами, мы хотим доказать, что существует такое сведбнне гс, вычислимое за полиномиальное время, что х Е Ь тогда и только тогда, когда схема В(з) выполнима. Идея доказательства — построить схему, моделирующую машину Тьюринга М, которая проверяет пары (х, и) (есловосвидетельствоь) для языка Ь, Входные переменные схемы будут представлять свидетельство и; при этом выполнимость схемы будет равносильна тому, что, машина М принимает пары (х, и) для некоторого ш.
Без потери общности, можно предположить следующее: 1. Алфавит машины М состоит из символов ~, 0,1 и пробела. 2. Время работы машины М не превышает 1(п), и используется память, не превосходящая в(п), где $(п) и з(п) — полиномы от и. 3. На всех входных словах длины а время работы машины М пючно равно $(п). Чтобы добиться этого нужно добавить строки вида (9т, х, ду, х, О) и (дн, х, дн, х,0) для всех х из алфавита и принудительно остановить машину после $(п) тактов работы.
Идея, на которой основана имитация работы машины М с помощью схемы, проиллюстрирована на рис. 3.12. Каждое внутреннее состояние машины Тьюринга представлено одним битом; обозначим эти биты Щ, дм..., д, дт, дн. Первоначально бит д, установлен в единицу, а все остальные биты, представляющие внутренние состояния, равны нулю. Каждая ячейка на ленте содержит три бита: два нз них представляют символ из алфавита (с., 0,1 или пробел), зе писанный в эту ячейку, третий является флагом, равным единице, если головка находится над ячейкой, и нулю в противном случае. Биты, представляющие содержимое ленты, будем обозначать (еш ие),..., (и,<„>, и,рй), а соответствующие флаги как уе,..., ~,~„р Существует также еще один бит Р, называемый глобальным флагом, смысл которого будет объяснен позже.
Первоначально Г равен нулю. Все входные биты мы рассматриваем как фиксированные, за исключением битов, представляющих слово-свидетельство и. 3.2. Анализ вычислительных задач 193 Выходной бнт йу раа Еакаитаианх аеиаи Епа ЗнФО атртианних аимянх атюа 4йиортатнинх 1 р а~ Ня) тактоа Рис. 3.12. Имитация машины Тьюринга с помощью схемы В схеме, имитирующей работу машины М, 1(п) рез повторяются фрагменты, каждый из которых имитирует один такт работы машины Тьюринга. Кажб дый такой фрагмент можно разбить на последовательность шагов, каждый из которых соответствует одной программной строке; в конце этой последовательности глобальный флаг Е устанавливается в нуль, как показано на рис. 3.13. Рис.
3.13. Схема, имитирующая один такт работы машины Тьюринга Чтобы завершить описание, нужно только объяснить, как именно программная строка (дс, х, дрз х', р) обрабатывается схемой. Предположим для удобства, 13' 196 Глава 3. Введение в информатику что д; ф д (аналогнчная конструкция работает и при 9; = д ). Итак, здесь нужно выполнить следующие действия: (1) Проверить, что $ = 1 (это указывает на то, что текущее состояние машины есть 9;).
(2) Для каждой ячейки ленты: (а) проверить, что глобальный флаг установлен в нуль (это означает, что машина Тьюринга еще ничего не сделала для выполнения данной программной строки); (6) проверить, что флаг, соответствующий этой ячейке, установлен в единипу (это указывает на то, что головка находится над данной ячейкой); (в) проверить, что содержимое этой ячейки есть х; (г) если все вышеперечисленные условия выполнены, то 1) установнть 9; = 0 и $ = 1, 2) установить содержимое ячейки в х', 3) обновить флаги данной и двух соседних ячеек в зависимости от значения е (+1, О, -1) и от того, находимся лн мы на краю ленты, 4) установить глобальный флаг в единипу, что указывает на то, что данный такт вычислений завершен.
Описанная в и. (2) процедура оперирует с фиксированным числом битов; ввиду установленного в подразд. 3.1.2 результата об универсальности эта процедура может быть реализована с помощью схемы с фиксированным числом используемых элементов. Легко видеть, что общее число элементов в схеме есть 0(1(п)(з(п) + и), т. е.
полиномиально. Ясно, что 9г = 1 тогда и только тогда, когда машина М принимает (я,ю). Таким обрезом, схема выполнима тогда и только тогда, когда М принимает (х, ю), и мы нашли искомое сведение Ь к СЯАТ. Задача СЯАТ открывает нам легкий путь к доказательству ХР-полноты многих других задач. Вместо того, чтобы доказывать ХР-полноту какой-либо задачи непосредственно, мы можем просто установить, что она принадлежит ХР и что задача СЯАТ к ней сводится. Тогда ввиду упражнения 3.22 наша задача также будет ХР-полной. Небольшая подборка ХР-полных задач приводится во вставке З.З. Примером еще одной ХР-полной задачи является задача емполнимоспию (ЯАТ), формулируемая в терминах булевых формул.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
