М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 51
Текст из файла (страница 51)
— Прим. ред. 200 Глава 3. Введение в информатику номиальная память дают нам ббльшую вычислительную эффективность, чем полиномиальное время. Однако, несмотря на серьезные усилия и изобретательность, проявленные различными исследователями, это так и не было доказано! В дальнейшем мы увидим, что класс задач, разрешимых на квантовом компьютере за полиномиальное время, содержится в РЯРАСЕ, так что доказательство того, что некоторая задача, эффективно разрешимая на квантовом компьютере, неразрешима при использовании классического компьютера, показало бы, что Р ф РЯРАСЕ и тем самым решило бы одну из важнейших проблем информатики. С оптимистической точки зрения это означает, что идеи квантовой теории вычислений могут быть использованы для доказательства того, что Р ф РЯРАСЕ. С пессимистической точки зрения можно заключить, что еще нескоро удастся строго доказать, что квантовые компьютеры могут эффективно решать задачи, практически неразрешимые на классическом компьютере.
Если быть еще ббльшим пессимистом, то можно предположить, что Р = РЯРАСЕ. В этом случае у квантовых компьютеров вообще нет никаких преимуществ перед классическими! Однако, вряд ли кто-нибудь из специалистов по теоретической информатике считает, что Р = РЯРАСЕ. Упражнение 3.23 (РЯРАСЕ С ЕХР). Класс сложности ЕХР (задачи, разрешимые за эксиокеиииаяэиое время) состоит из задач разрешения, которые могут быть решены на машине Тьюринга за время 0(2" ), где к — какая-либо константа.
Докажите, что РЯРАСЕ С ЕХР. (Указание. Если машина Тьюринга использует 1 внутренних состояний, алфавит из т букв и память размера р(и), то общее число ее состояний не превышает 1т"!"1, а так как она не зацикливается, то не может попасть в одно и то же состоянне дважды.) 'Упражнение 3.26 (Ь С Р). Класс сложности Ь (логарифмическая память) состоит из задач разрешения, которые могут быть решены на машине Тьюринга с использованием логарифмической памяти, т. е. памяти размера 0(!об и). Точнее говоря, класс Ь определяется с помощью двухленточной машины Тьюринга. Одна лента содержит входные данные (размера и) и на нее нельзя ничего записывать; допустимы только программные строки, не меняющие ее содержимого. Другая лента — это рабочая лента, изначально содержащая только пробелы; требование логарифмической памяти накладывается только на эту рабочую ленту.
Покажите, что Ь С Р. Повысится ли эффективность вычислений, если разрешить использовать больше времени или больше памяти? Ответ на этот вопрос положителен в обоих случаях. Грубо говоря, теорема о ерсменнбй иерархии утверждает, что класс Т1МЕ(у(и)) является собственным подклассом Т1МЕ(Дп) !об~ !(и)). Аналогичным образом теорема об иерархии по памяти гласит, что класс ЯРАСЕ(у(и)) является собственным подклассом ЯРАСЕЩп) 1ойу(п)), где, конечно, ЯРАСЕ(у(и)) — это класс языков, распознаваемых на памяти 0(у(п)). Эти теоремы об иерархии имеют интересные следствия, касающиеся отношений между сложностными классами. Известно, что (3.1) Ь с Р с 1ч?Р ~ РЯРАСЕ с ЕХР. К сожалению, хотя общепринято, что каждое из этих включений является 3.2.
Анализ вычислительных задач 201 строгим, ни про одно из них это не доказано. Однако из теоремы о временнбй иерархии следует, что Р является собственным подклассом ЕХР, а из теоремы об иерархии по памяти следует, что Ь является собственным подклассом РЯРАСЕ! Таким образом, можно заключить, что хотя бы одно из включений в (3.1) является строгим, хотя мы и не знаем, какое именно. Что можно сделать с задачей, про которую мы знаем, что она является ХР-полной (или выполняется какой-либо другой критерий трудности)? Оказывается, что на этом анализ задачи далеко не кончается.
Один из возможных подходов заключается в том, чтобы выделить частные случаи задачи, которые можно все-таки эффективно решить. В упр. 3.24 мы видели, что задача 2ЯАТ имеет эффективное решение, несмотря на то, что задача ЯАТ является ХР-полной. Другой подход состоит в том, чтобы изменить трактовку понятия «решение задачи» вЂ” при этом обычно получаются определения новых классов сложности. Например, вместо точного решения ХР-полной задачи можно искать ее приблпжеиное решение.
Например, задача о вершинном покрытии является ХР-полной. Однако в упр. 3.27 мы показываем, что можно эффективно найти вершинное покрытие, в котором количество вершин не более чем вдвое превьппает количество вершин в оптимальном вершинном покрытии. С другой стороны, в задаче 3.6 мы покажем, что для задачи коммивояжера невозможно найти приближенное решение, отличающееся от оптимального не более, чем на любой фиксированный множитель (если, конечно, Р ф ХР). эгпражнение 3.27 (приближенное решение задачи о вершинном покрытии).
Пусть С = Я Е) — неориентированный граф. Докажите, что приведенный ниже алгоритм находит вершинное покрытие для С, число вершин в котором не более, чем вдвое превосходит минимально возможное. УС= о Е' = Е бо шпй Е' = а пусть (а,1?) †произвольн ребро вз Е' УС = УС О(а,1?) удалить из Е' все ребра, инпидентные а или 1? геФогп ЧС Почему у одних ХР-полных задач приближенные решения существуют, а у других — нет? Ведь, казалось бы, возможно эффективное сведбние одних задач к другим? Это, бесспорно, так, но сведение не обязательно переводит хорошие приближения в хорошие.
В результате анализ приближенных алгоритмов для задач из класса ХР оказывается более сложным. На эту тему существует целая теория, которая, к сожалению, выходит за рамки нашей книги. Основная идея тут в том, чтобы определить новое понятие сводимости, при котором сохраняются хорошие приближения. Имея в виду такую сводимость, можно определить класс сложности МАХЗХР, аналогичный классу ХР, как множество задач, для которых можно эффективно проверить приближенное решение.
Для класса МАХЗХР, как и для ХР, существуют полные задачи; 202 Глава 3. Введение в информатику интересный открытый вопрос — выяснить, как класс МАХЯХР соотносится с классом задач, для которых имеется эффективное приближенное решение. Мы завершим наше обсуждение примером класса сложности, определение которого основано на измененной вычислительной модели. Предположим, что машина Тьюринга наделена способностью бросать монету и использовать результат такого бросания для того, чтобы решать, какое действие произвести в процессе вычислений. Такая машина Тьюринга может принимать или отвергать входные данные только с некоторой вероятностью.
Класс сложности ВРР (еероягяностпные вычисления, за пояиномиояьное еремя и с ограниченными ошибками) состоит из языков Ь, для которых существует такая вероятностная машина Тьюринга М, что при х е Ь она принимает х с вероятностью не менее 3/4, а при х ф Г отвергает х с вероятностью не менее 3/4 (за полиномиальное время в обоих случаях). Следующее упражнение показывает, что выбор 3/4 в качестве константы по существу произволен. 'Упражнение 3.28 (незавнсимость класса ВРР от выбора константы). Пусть я — фиксированное число, 1/2 ( й < 1, и пусть язык Ь таков, что существует машина Тьюринга М, которая при х Е Ь принимает х с вероятностью не менее Й, а при х ф Ь отвергает х с вероятностью не менее Й (за полиномиальное время в обоих случаях).
Покажите, что Ь б ВРР. На самом деле неравенство Чернова, обсуждаемое во вставке 3.4, показывает, что после нескольких повторений алгоритма, распознающего язык из класса ВРР, вероятность успеха может быть увеличена до значения, которое для всех практических целей можно считать равным единице. По этой причине класс ВРР можно даже в большей степени, чем класс Р, считать классом задач, эффективно разрешимых на классическом компъютере, и именно квантовый аналог класса ВРР, известный как Вь4Р, будет нам наиболее интересен при изучении квантовых алгоритмов.
3.2.5 Вычисления и энергия Теория сложности вычислений изучает, сколько времени и памяти тратится на решение вычислительной задачи. Другой важный вычислительный ресурс— это энергия. В этом подразделе мы изучим, сколько энергии требуется для вычислений. Удивительно, что вычисления (как классические, так и квантовые) можно в принципе проводить без энергетических затрат! Потребление энергии при вычислениях оказывается глубоко связанным с обратиимостиью вычнсль ний. Рассмотрим элемент, например НАИВ, получающий на вход два бита и выдающий один бит на выходе. Этот элемент по сути своей необрашим, поскольку вход невозможно однозначно определить по выходу.
Если, например, на выходе получена 1, на входе могло быть и 00, и 10, и 01. С другой стороны, НОТ вЂ” пример обрагяимого элемента, поскольку по его выходу можно определить, каков был вход. Другой способ представлять себе необратимость — это рассматривать ее в терминах уничтожения информации.
Если логический элемент необратим, то 3.2. Анализ вычислительных задач 203 Вставка 3.4. ВРР и неравенство х1ернова Пусть у нас есть алгоритм, дающий правильный ответ с вероятностью 1/2+ с и неверный ответ с вероятностью 1/2 — с. Если запустить этот алгоритм и раз, то представляется естественным, что правильный ответ — этот тот, который появляется наиболее часто. Насколько надежна зта процедура? Нераееисгпео Чернова — это простой результат из элементарной теории вероятностей, дающий ответ на этот вопрос. Теорема 3.3(Неравенство 'Чернова). Пусть Хм...,Մ— независимые и одинаково распределенные случайные величины, каждая из которых принимает значение 1 с вероятностью 1/2 + с и значение 0 с вероятностью 1/2 — с.
Тогда (3.2) р(Х1 = хы...,Х„= х„) < ~- — е/ ~-+с/ (3.3) (1 — 4ез) У (3.4) Число таких последовательностей не превышаег 2", так что р ) Х( < и/2 < 2" х = (1 — 4е~)т / " '1 „(1-4сз) 3 ьм (3.5) Наконец, из математического анализа известно, что 1 — л < ехр( — х), так что р ~~~ ~Х, < /2 < с ы~пlз е за~а (3.6) Все это говорит о том, что для фиксированного е вероятность ошибки экспоиенциально рбыеаети с ростом числа повторений алгоритма.
В случае ВРР имеем с = 1/4, так что после всего лишь нескольких сотен повторений вероятность ошибки будет меньше, чем 10 зс, и тут уже ошибки в работе компьютера становятся более значимыми, чем ошибки, обусловленные вероятностным характером алгоритма. Доиазатпельство. Рассмотрим произвольную последовательность (хм..., х„), содержащую не более п/2 единиц. Вероятность появления такой последовательности максимальна, когда она содержит (и/2) единиц, так что 204 Глава 3.
Введение в информатику часть информации, подаваемой на его вход, безвозвратно пропадает в результате его работы, т. е. уничтожается этим элементом. При обратимых вычислениях, напротив, никакая информация не уничтожается, поскольку вход всегда может быть восстановлен по выходу. Другими словами, обратимое вычисление — это вычисление, не уничтожающее информацию. Как связаны потребление энергии и необратимость вычислений? Эта связь описывается иринцивоз«Ландауэра, утверждающим, что при уничтожении информации неизбежно происходит диссипация энергии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
