М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 48

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

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

Во всех остальных отношениях машина ведет себя по- прежнему, а останавливается, когда приходит в состояние оу или он. Язык Ь распознается машиной Тьюринга, если машина может определить, принадлежит ли входное слово языку Ь, следующим образом: она останавливается в состоянии оу, если х б Ь, и останавливается в состоянии он, если х ф Ь. Мы будем говорить, что машина приняла или отвергла слово х в зависимости от того, какое из этих событий произошло. Как быстро сможем мы определить, является ли число простым? Другими словами, какова максимальная скорость машины Тьюринга, распознающей 3.2. Анализ вычислительных задач 189 язык, который соответствует задаче определения простоты? Будем говорить, что задача принадлежит классу Т1МЕЩО)), если существует машина Тьюринга, выясняющая, принадлежит ли слово х данному языку, за время 0(ДО) ), где П вЂ” длина х.

Говорят, что задача разрешима за на«иномиальное время, если она принадлежит классу Т1МЕ(пь) для некоторого конечного й. Множество всех языков, принадлежащих классу Т1МЕ(пь) для некоторого л, обозначается Р. Класс Р— это наш первый пример класса сложности.

Вообще, класс сложности — это некоторое множество языков. Значительная часть теории сложности состоит в определении различных классов сложности и выяснении отношений между ними. Не удивительно, что существуют задачи, неразрешимые за полиномивльное время. К сожалению, доказательство того, что какая-то конкретная задача неразрешима за полиномивльное время, представляется очень трудным, хотя существует очень много гипотез.

Простым примером интересной задачи разрешения, про которую принято считать, что она не принадлежит классу Р, является задача о существовании делителя. ЗАДАЧА О сУЩестВОВАнии ДелителЯ. ДанО сосгавнОе числО т и целое число 1 ( т. Есть ли у числа т нетривиальный делитель, меньший, чем 1? Интересным свойством этой задачи является то, что если кто-то заявит «Да, у числа т есть нетривиальный делитель, меньший, чем Ь, то истинность этого утверждения может быть эффективно проверена делением в столбик. Мы будем называть такой делитель свидетельством в пользу того, что у т есть делитель, меньший, чем 1.

Это понятие легко проверяемого свидетельства лежит в основе определения класса сложности ХР, которое будет дано ниже. Мы сформулировали задачу о существовании делителя как задачу разрешения, но легко проверить, что эта задача эквивалентна разложению числа на простые мнОжители: Упражнение 3.1?. Докажите, что алгоритм, выполняющий задачу разложения числа т на простые множители за полиномиальное время, существует тогда и только тогда, когда задача о существовании делителя принадлежит классу Р.

Задача о существовании делителя — пример задачи разрешения, принадлежащей важному классу сложности, известному под назвэлием ХР. Задачи класса ХР характерны тем, что в них ответ «да» может быть легко проверен с помощью подходящего свидетельства. Точнее говоря, язык Ь принадлежит классу ХР, если существует машина Тьюринга М со следующими свойствами: 1. Если х Е Ь, то существует такая строка (свидетельство) ш, что М останавливается в состоянии оу через время, полиномиальное по ~х~, если в момент запуска машины на ленте записана строка х, пробел, а затем ш.

2. Если х ф Ь, то для любой строки и машина останавливается в состоянии дн через время, полиномиэльное по )х~, если в момент запуска на ленте стоит х, пробел и и. 190 Глава 3, Введение в информатику В определении класса ХР есть интересная асимметрия. В то время как мы должны иметь возможность'быстро проверить, действительно ли данное свидетельство в пользу того, что х Е Ь, истинно, у нас нет необходимости предъявлять свидетельство в пользу того, что х ф Ь. В задаче о существовании делителя мы можем легко убедиться, что данное число имеет делитель, меньший тп, но нахождение свидетельства в пользу того, что у числа нет делителей, меньших тп, более серьезная задача.

Эта асимметрия подсказывает определение класса соХР, а именно класса языков, допускающих свидетельства в пользу ответа «нет»; очевидно, что соХР-языки являются дополнениями к 1ЧР-языкам. Как связаны классы Р и ХР? Ясно, что Р является подмножеством 1ЧР; самая знаменитая нерешенная проблема в теории сложности — вьттснитпь, сущесптвтротп ли ХР-задачи, не принадлежащих классу Р; часто эту проблему называют просто Р ф ХР.

Большинство специалистов по информатике счита.- ет, что Р ~ 1«Р, но, несмотря на десятилетия работы, никому не удалось это доказать, и остается возможность того, что Р = МР. Упражнение 3.13. Докажите, что если соГЧР ф 1ЧР, то и Р ф 1ЧР. При первом знакомстве с проблемой Р ф 1чР возникает впечатление, что решить ее совсем просто. Чтобы понять, почему на самом деле эта проблема довольно тонкая, полезно рассмотреть несколько примеров задач, принадлежащих классам Р и ХР. Мы будем брать примеры из тпеории графов, являющейся богатым источником задач разрешения, имеющих удивительно много практических приложений.

Графом называется конечное множество вершин (ом..., оа), соединенных ребрами, которые задаются парами вершин (оно ). Здесь мы будем рассматривать только нвориентпированньье графы, в которых порядок вершин в каждой из этих пар не играет роли; аналогичным образом могут быть рассмотрены ориентпированнме графы, в которых порядок вершин имеет значение. Типичный граф изображен на рис. 3.9. Рис. 3.9. Граф. Цик«в графе — это такая последовательность вершин ом..., о„„что каждая пара (ит, стет), а также пара (ом о ), являются ребрами.

Простпоа цикл— зто цикл, в котором вершины, кроме первой и последней, не повторяются. Гамильтонов цикл — это простой цикл, в который входят все вершины графа. 3.2. Анализ вычислительных задач 191 Примеры графов, обладающих и не обладающих гамильтоновыми циклами, приведены на рис. 3.10. Рис. 3.10. Левый граф содержит гамильтонов цикл 0,1,2,3,4,5,0.

Граф справа гамильтонова цикла не содержит, что может быть проверено перебором. Задача о гамильглоноеом цикле (НС) состоит в том, что надо выяснить, обладает ли данный граф гамильтоновым циклом. НС вЂ” это задача разрешения, принадлежащая классу ХР, поскольку если гамильтонов цикл у данного графа есть, то он может быть использован в качестве легко проверяемого свидетельства.

Более того, для задачи НС не известно никакого полиномиального алгоритма. На самом деле НС относится к классу так называемых ХР-полных задач, которые могут рассматриваться как «самые трудныеь в классе ХР: если задачу НС можно решить за время $, то любая другая задача из класса ХР может быть решена за время 0(ро1у($)). Это означает также, что если какая-либо ЖР-полная задача имеет решение за полиномиальное время, то Р = ХР. Существует другая задача разрешения — задача об эйлеровом цикле, которая, несмотря на поверхностное сходство с задачей о гамильтоновом цикле, имеет совершенно другие свойства.

Эйлеров цикл — это цикл в графе, в котором каждое ребро проходится ровно один раз. Задача об эйлеровом цикле (ЕС) состоит в том, что для данного графа 0 с п вершинами надо выяснить, есть ли у него эйлеров цикл. Таким образом, формулировка у задачи ЕС такая же, как у НС, только с заменой вершин на ребра. А теперь давайте посмотрим на следующую замечательную теорему, которую мы предложим вам доказать в упражнении 3. 20. Теорема 3.1 (теорема Эйлера). Связный граф содержит эйлеров цикл тогда и только тогда, когда из каждой вершины исходит четное число ребер. Теорема Эйлера дает нам метод эффективного решения задачи ЕС.

Бо-первых, надо проверить, является ли граф связным; это легко сделать за 0(п~) операций (см. упр. 3.19). Если граф не связен, то, очевидно, что эйлерова цикла нет. Если граф связен, то для каждой вершины надо проверить, четко ли число исходящих из нее ребер. Если найдена вершцна, для которой это не так, то эйлерова цикла нет, в противном случае он существует.

Поскольку в графе и вершин и не более п(п — 1)/2 ребер, этот алгоритм использует 0(пз) элементарных операций. Следовательно, задача ЕС принадлежит классу Р1 В задаче обхода ребер скрыта какая-то структура, которой можно воспользоваться для 192 Глава 3. Введение в информатику создания эффективного алгоритма, решающего задачу ЕС, но в задаче обхода вершин такой структуры по-видимому, нет.

Совершенно не очевидно, почему такая структура есть в одной задаче и нет в другой (если, конечно, в задаче НС ее действительно нет). Упражнение 3.19. Задача о достижимости состоит в том, что надо выяснить, существует ли путь, соединяющий две данные вершины графа. Покажите, что задачу достижимости можно решить за 0(п) операций, если граф содержит и вершин.4 Воспользуйтесь решением задачи о достижимости для доказательства того, что можно за 0(пз) операций выяснить, связен ли граф.

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

Список файлов книги