М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 50
Текст из файла (страница 50)
Напомним, что булева формула <р строится из следующих элементов: булевых переменных хм хе,..., булевых связок, т. е. булевых функций Л (АНП), Ч (ОК) и . (НОТ), и скобок. Истинность илн ложность булевой формулы при данных значениях булевых переменных устанавливается по обычным правилам булевой алгебры. Например, формула 1с = х~ ~/ хэ выполняется при х~ = 0 3.2. Анализ вычислительных задач 197 и хз = О и не выполняется при хт = О и хз = 1.
Задача выполнимости состоит в том, чтобы установить, будет ли данная булева формула 1в истинной при каких-нибудь значениях переменных. Упражнение 3.23. Покажите, что задача ЯАТ ХР-полна, доказав, что она принадлежит ХР и что СЯАТ к ней сводится. (Указание. Для сведбния может быть полезно представить каждый провод в виде отдельной переменной в булевой формуле.) Важным частным случаем задачи ЯАТ также является ЫР-полная задача 3-выполнимости (ЗЯАТ), относящаяся к формулам в 3-конеюнктаивной нормальной форме. Говорят, что формула представлена в квнеюнжтвивнвй нормальной форме, если она является конъюнкцией набора дизеюннтавв, каждый из которых в свою очередь представляет собой дизъюнкцию одного или нескольких литпералсв, где литерал — выражение вида х или .
х. Например, формула (- хт ч хэ ч хз) л (- х~ ч хз ч . хл) л (хэ ч хз ч хл) представлена в 3-конъюнктивной нормальной форме. Задача 3-выполнимости состоит в том, чтобы выяснить, выполнима ли данная формула, представленная в 3-конъюнктивной нормальной форме. Доказательство того, что задача ЗЯАТ является МР-полной, проводится непосредственно, но оно слишком длинное, чтобы можно было включить его в этот обзор. Задача ЗЯАТ является в некотором смысле ИР-полной задачей даже в большей степени, чем СЯАТ и ЯАТ, и именно на ее ХР-полноте основаны бесчисленные доказательства 1чР-полноты конкретных задач. Мы завершим наше обсуждение МР-полноты тем удивительным фактом, что задача 2ЯАТ, аналог ЗЯАТ, в которой каждый дизъюнкт состоит из двух литералов, разрешима за полиномиальное время. Упражнение 3.24 (у задачи 2ЯАТ есть эффективное решение). Пусть <р — булеза формула в конъюнктивной нормальной форме, в которой каждый двзъюнкт содержит только два литерала.
(1) Постройте ориентированный граф С(у) следующим образом. Вершины С соответствуют переменным х и их отрицаниям . х", ребро соединяет о и )3 тогда и только тогда, когда 1о содержит дизъюнкт вида (-о Ч 17) или (13 Ч вЂ” о). Покажите, что ю не является выполнимой тогда и только тогда, когда для некоторой переменной х в графе С существует как путь нзхв х,такипутьиз хвх. (2) Докажите, что для данного ориентированного графа с п вершинами можно за полиномиальное время выяснить, существует ли путь из данной вершины и~ в данную вершину съ (3) Постройте эффективный алгоритм, решающий задачу 2ЯАТ.
Если предположить, что Р 44 МР, то можно доказать, что существует нвпуствой класс ХР1, состоящий, по определению, из задач, не являющихся ни разрешимыми за полиномиальное время, ни 1чР-полными. Разумеется, ни про одну задачу не доказано, что она принадлежит классу ХР1 (иначе мы знали 198 Глава 3. Введение в информатику Вставки 3.3.
Примеры ХР-полных задач Класс ХР важен, в частности, и потому, что огромное количество задач принадлежит этому классу. Мы даже и не пытаемся дать здесь полный обзор (см. раздел «История и дополнительная литература»); приводимые ниже примеры, взятые из многих различных разделов математики, дают представление о необычайном разнообразии ХР-полных задач. ° ЗАДАЧА О клике (творил графов). Кликой в (неориентированном) графе С называется множество вершин, каждая пара из которых соединена ребром; число вершин в этом множестве называется рагмераи клики.
Дано целое число т и граф С; содержит ли С клику размера т? ° ЗАдАчА О суммАх пОдмнОжестВ (арифметика). Дано конечное множество о', состоящее из целых положительных чисел, и число 1. Существует ли в о' подмножество, сумма элементов которого равна $? ° 0-1 ЦелОчисленнОе пРОГРАммиРОВАние (линейное программирование). Даны целочисленная (т х и)-матрица А и т-мерный целочисленный вектор у; существует ли такой и-мерный вектор з, координаты которого принадлежат множеству (О, 1), что Аз < у? ° ВЕРШИННОЕ ПОКРЫТИЕ (теория графов). Вершинным покрытием неориентированного графа С называется такое множество вершин Г, что у каждого ребра хотя бы одна вершина содержится в Ъ".
Для данных целого числа т и графа С существует ли у графа С вершинное покрытие, содержащее т вершин? бы, что Р гг ХР), но есть несколько задач, считающихся кандидатами на принадлежность к этому классу. Два наиболее вероятных кандидата — это задача о существовании делителя и задача об изоморфизме графов. ЗАдАчА ОВ изомОРФизме ГРАФОВ, Пусть С и С' — неориентированные графы с множеством вершин 'г' = (вг,..., и„).
Являются ли графы С и С' изоморфными? Другими словами, существует ли такое взаимно однозначное отображение уп Ъ' -» Ъ", что ребро (ио иу) содержится в С тогда и только тогда, когда ребро (у(иг), Ф(и )) содержится в С'? Задачи класса ХР1 интересны для специалистов по квантовым вычислениям и квантовой теории информации по двум причинам. Во-первых, желательно найти быстрые квглтовые алгоритмы для заллч, не принадлежащих Р. Во-вторых, многие считают, что квантовые компьютеры не смогут эффективно решать все задачи из класса ХР, включая ХР-полные задачи.
Поэтому естественно сосредоточиться на классе ХР1. И действительно быстрый квантовый алгоритм разложения на множители найден (гл. 5), что побуждает искать 3.2. Анализ вычислительных задач 199 быстрые квантовые алгоритмы для других задач, предположительно принад- лежащих МР1. 3.2.4 Другие классы сложности Мы рассмотрели элементарные свойства некоторых важных классов сложности. На самом деле этих классов очень много, и между ними имеется множество доказанных или гипотетических нетривиальных соотношений. Для исследователей в области квантовых вычислений и квантовой теории информации нег необходимости знать все различные классы сложности, но важно иметь представление о наиболее важных из них, у многих из которых есть квантовые аналоги.
Далее, если мы хотим выяснить вычислительные возможности квантовых компьютеров, то надо понять, как класс задач, разрешимых на квантовых компьютерах, вписывается в иерархию классов сложности, определенных для классических компьютеров. При определении классов сложности можно учитывать три параметра: интересующий нас ресурс (время, память... ), тип рассматриваемых задач (задачи разрешения, задачи оптимизации...) и используемая вычислительная модель (детерминированная машина Тьюринга, вероятностная машина Тьюринга, квантовый компьютер...
). Не удивительно, что при этом получаются определения огромного числа классов сложности. В этом разделе мы коротко обсудим несколько наиболее важных из них, а также их элементарные свойства. Начнем мы с класса сложности, получаемого, если задать ограничения не на время, а на памятпь. Наиболее естественный из классов сложности, определяемых с использованием ограничений на память, — это класс РБРАСЕ, состоящий из задач разрешения, которые могут быть решены на машине Тьюринга с учетом полиномиального количества рабочих битов, но без ограничений на время работы (см. упр. 3.25). Очевидно, что Р содержится в РЯРАСЕ, поскольку машина Тьюринга, останавливающаяся за полиномиальное время, может использовать только полиномиальное количество ячеек. Кроме того, в РЯРАСЕ также содержится класс ХР. В самом деле, пусть Ь вЂ” язык класса ХР.
Предположим, что у задач размера и имеется свидетельство размера, не превосходящего р(п), где р(п) — полипом от п.в Чтобы выяснить, есть ли у задачи решение, можно последовательно проверить все 2в~в> возможных свидетельств. Каждая проверка может быть проведена за полиномнальное время, и тем самым с использованием полиномиальной памяти. Если будем стирать все промежуточные вычисления перед очередной проверкой, то проверим все возможности, используя лишь полиномиальную память. К сожалению, в настоящее время неизвестно даже, содержит ли РЯРАСЕ задачи, не принадлежащие Р! Эта ситуация весьма замечательна: представляется совершенно очевидным, что неограниченные временные ресурсы и поли- е Хоровым упражнением будет доказательство существования такого короткого свидетельстжк ведь в данном выше определении класса 1ЧР ничего не говорится о длине записи шидетельства.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
