Классические и квантовые вычисления

 

Столичный Бизнес Колледж

Факультет: «КОМПЬЮТЕРНЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИИ»

Курсовая работа

По Операционным системам и средам

На тему:

«Классические и квантовые вычисления»

Выполнил: Студент 3 курса:

Михайлов М.А.

Москва

г.

Раздел №0. Введение. Предисловие

В последние годы интерес к тому, что называется "квантовые компьютеры", необычайно возрос. Идея использования возможностей квантовой механики при организации вычислений выглядит все более привлекательной, начаты экспериментальные работы в этой области.

Однако перспективы физической реализации квантовых компьютеров пока совершенно неясны. Скорее всего, это дело нескольких десятилетий. Основные достижения в этой области носят пока чисто математический характер.

Эта книга предназначена для первоначального знакомства с математической теорией квантовых вычислений. Для удобства читателя вначале дается краткое введение в классическую теорию сложности вычислений. Затем подробно излагаются основы теории квантовых вычислений, включая описание основных известных к настоящему времени эффективных квантовых алгоритмов.

Основу книги составили материалы курса "Классическое и квантовое вычисление", прочитанного А. Шенем (классические вычисления) и А. Китаевым (квантовые вычисления) в Высшем колледже математики Независимого Московского университета в весеннем семестре 1998 г. При подготовке книги также использовались материалы курса Physics 229 - Advanced Mathematical Methods of Physics (Quantum computation), который вели Дж. Прескилл (John Preskill) и А. Китаев (при участии А. Ландала (Andrew Landahl)) в Калифорнийском технологическом институте в 1998-1999 уч. г.

Необходимые для чтения этой книги знания невелики. В сущности, достаточно знания линейной алгебры в объеме стандартного университетского курса, элементарной теории вероятностей, элементарной теории чисел и минимальных представлений о теории алгоритмов (например, иметь навыки практического программирования нетривиальных алгоритмов).

Обозначения

дизъюнкция (логическое ИЛИ)

конъюнкция (логическое И)

отрицание

сложение по модулю 2 (а также прямая сумма линейных пространств)

импликация (логическое следование)

логическая эквивалентность

множество конечных слов в алфавите

пустой символ (пробел) в алфавите машины Тьюринга

функция переходов машины Тьюринга

сводимость предикатов по Карпу ( сводится к ) (лекция 2 <#"22" src="doc_zip14.jpg" /> существует такое число , что

существует такое число , что

то же самое, что

конечное поле из элементов

кольцо вычетов по модулю

аддитивная группа кольца

мультипликативная группа обратимых элементов

( ) - группа характеров абелевой группы

симплектическая группа над полем размерности (лекция 14 <#"22" src="doc_zip36.jpg" /> расширенная симплектическая группа над полем размерности (лекция 14 <#"16" src="doc_zip39.jpg" /> множество комплексных чисел

комплексное сопряжение

группа унитарных операторов на пространстве

специальная унитарная группа на пространстве

специальная ортогональная группа на евклидовом пространстве

пространство, порожденное векторами

пространство линейных функционалов на пространстве

-я тензорная степень

пространство линейных операторов на

пространство линейных отображений из в

классический бит (множество

квантовый бит (q-бит, пространство )

бра-вектор (лекция 5 <#"22" src="doc_zip63.jpg" /> кет-вектор (лекция 5 <#"22" src="doc_zip64.jpg" /> скалярное произведение

эрмитово сопряженный оператор

обратимое копирование бита (Controlled NOT) (лекция 6 <#"19" src="doc_zip67.jpg" /> обратимая функция, соответствующая булевой функции (лекция 6 <#"18" src="doc_zip69.jpg" /> тождественный оператор на пространстве

унитарный оператор, соответствующий перестановке (лекция 6 <#"22" src="doc_zip73.jpg" /> оператор с квантовым управлением (лекция 7 <#"18" src="doc_zip75.jpg" /> проектор (оператор проектирования) на подпространство

базисные операторы на пространстве (лекция 14 <#"16" src="doc_zip79.jpg" /> преобразование матриц плотности (лекция 14 <#"22" src="doc_zip81.jpg" /> оператор, действующий на квантовый регистр (множество q-битов) (лекция 5 <#"18" src="doc_zip83.jpg" /> частичный след от оператора по пространству (лекция 9 <#"22" src="doc_zip86.jpg" /> норма вектора (лекция 7 <#"22" src="doc_zip87.jpg" /> следовая норма (лекция 14 <#"22" src="doc_zip88.jpg" /> норма для преобразований матриц плотности (лекция 14 <#"22" src="doc_zip89.jpg" /> мощность множества или модуль числа

символ Кронекера

характеристическая функция множества

наибольший общий делитель и

сравнение по модулю

остаток по модулю

представление рационального числа в виде несократимой дроби

вероятность события

условная вероятность (в различных контекстах)

квантовая вероятность (лекция 9 <#"92" src="doc_zip106.jpg" />

Обозначения сложностных классов

(лекция 1 <#"18" src="doc_zip107.jpg" /> (лекция 4 <#"18" src="doc_zip108.jpg" /> (лекция 4 <#"justify">Введение

Все компьютеры, начиная от так и не построенной "аналитической машины" Чарльза Бэббиджа1) <#"16" src="doc_zip109.jpg" />или ), а программа - это последовательность операций, каждая из которых использует небольшое число битов. Конечно, новые компьютеры работают быстрее старых, но прогресс в этом направлении имеет предел. Трудно предположить, что размер транзистора или аналогичного элемента будет меньше см (диаметр атома водорода), а рабочая частота - больше ~Гц (частота атомных переходов). Так что даже суперкомпьютеры будущего не смогут решать вычислительные задачи, имеющие экспоненциальную сложность. Рассмотрим, например, задачу о разложении целого числа на простые множители. Очевидный способ - это попробовать разделить на числа от до . Если число имеет знаков в двоичной записи, то придется перебрать вариантов. Существует хитроумный алгоритм, решающий ту же задачу примерно за шагов ( ). Даже в этом случае, чтобы разложить на множители число из миллиона знаков, не хватит времени жизни Вселенной. (Возможно, есть и более эффективные алгоритмы, но от экспоненты, по-видимому, избавиться не удастся.)

Существует, однако, другой способ ускорить процесс вычисления для некоторых специальных классов задач. Дело в том, что обычные компьютеры не используют всех возможностей, предоставляемых природой. Это утверждение может показаться слишком очевидным: в природе есть множество процессов, совершенно непохожих на операции с нулями и единицами. Можно попытаться использовать эти процессы для создания аналоговой вычислительной машины. Например, интерференция света может использоваться для вычисления преобразования Фурье. Однако в большинстве случаев выигрыш в скорости не является принципиальным, т.е. слабо зависит от размера устройства. Причина заключается в том, что уравнения классической физики (например, уравнения Максвелла) эффективно решаются на обычном цифровом компьютере. Что значит эффективно? Вычисление интерференционной картины может занять в миллионы раз больше времени, чем реальный эксперимент, потому что скорость света велика, а длина волны мала. Однако с увеличением размера моделируемой физической системы количество необходимых вычислительных операций растет не слишком быстро - степенным, или, как принято говорить в теории сложности, полиномиальным образом. (Как правило, число операций пропорционально величине , где - объем, а - время.) Таким образом, классическая физика слишком "проста" с вычислительной точки зрения.

Квантовая механика устроена в этом смысле гораздо интереснее. Рассмотрим, например, систему из спинов. Каждый спин обладает двумя базисными состояниями ( и ), а вся система имеет базисных состояний (каждая из переменных принимает значение или ). Согласно общим принципам квантовой механики, возможными состояниями системы являются также суперпозиции вида , где - комплексные числа, называемые амплитудами. Знак суммы здесь нужно понимать чисто формально. Суперпозиция является новым математическим объектом - вектором в -мерном комплексном пространстве. Квадрат модуля амплитуды, , равен вероятности обнаружить систему в базисном состоянии при измерении значений переменных . (Отметим, что такое измерение разрушает суперпозицию.) Следовательно, должно выполняться условие . Итак, общее состояние системы (т.е. суперпозиция) - это вектор единичной длины в -мерном комплексном пространстве. Изменение состояния за определенный промежуток времени описывается унитарной матрицей размера . Если промежуток времени очень мал ( , где - энергия взаимодействия), то эта матрица устроена достаточно просто; каждый из ее элементов можно легко вычислить, зная взаимодействие между спинами. Если же мы хотим узнать изменение состояния системы за большой промежуток времени, то придется перемножать такие матрицы. Для этого требуется экспоненциально большое число операций. В настоящее время неизвестно никакого способа упростить данное вычисление, скорее всего, моделирование квантовой механики является экспоненциально сложной вычислительной задачей. Однако то же самое утверждение можно сформулировать иначе: квантовая система эффективно "решает" сложную вычислительную задачу - моделирует саму себя.

Можно ли использовать квантовые системы для решения других вычислительных задач? Какова должна быть математическая модель квантового компьютера, в той же степени не зависящая от физической реализации, что и модели классических вычислений2) <#"16" src="doc_zip144.jpg" />спинов, каждый из которых находится в отдельном ящичке и идеально изолирован от окружающего мира. В каждый момент времени мы можем выбрать, по нашему усмотрению, любые два спина и подействовать на них любой унитарной матрицей . Последовательность таких операций называется квантовой схемой. Каждая операция определяется парой номеров спинов и шестнадцатью комплексными числами, поэтому квантовую схему можно записать на бумаге. Это своего рода программа для квантового компьютера.

Чтобы использовать квантовую схему для вычисления функции3) <#"16" src="doc_zip146.jpg" />, нужно уметь вводить входные данные, проделывать вычисления и считывать результат. Ввести в квантовый компьютер последовательность нулей и единиц - значит приготовить начальное состояние . (Объем входных данных обычно меньше общего количества "ячеек памяти", т.е. спинов, . Оставшиеся ячейки заполняются нулями.) К начальному состоянию применяется квантовая схема, зависящая от решаемой задачи, но не от конкретных входных данных. В итоге возникает квантовое состояние

зависящее от . Теперь нужно считать результат. Предполагаем, что ответ должен содержаться в первых битах строки , т.е. мы ищем такие , что . Для получения ответа производится измерение значений всех спинов. Результатом измерения может быть любая последовательность нулей и единиц , вероятность получить ее равна . Таким образом, квантовый компьютер может, с некоторой вероятностью, дать любой ответ. Квантовая схема является "правильной" для данной функции , если правильный ответ получается с вероятностью, достаточно близкой к единице. Повторив все вычисление несколько раз и выбрав тот ответ, который встречается чаще, можно снизить вероятность ошибки до сколь угодно малой величины.

Мы только что сформулировали (опуская некоторые подробности) математическую модель квантового вычисления. Теперь естественно задать два вопроса.

Для каких задач квантовое вычисление дает выигрыш по сравнению с классическим?

Какую систему можно использовать для физической реализации квантового компьютера? (Это не обязательно должна быть система спинов.)

По поводу первого вопроса сейчас известно следующее. Во-первых, на квантовом компьютере можно моделировать любую квантовую систему за полиномиальное число шагов. Это позволит (при наличии квантового компьютера) предсказывать свойства молекул и кристаллов, проектировать микроскопические электронные устройства размером в несколько десятков ангстрем. (Сейчас такие устройства находятся на пределе технологических возможностей, но в будущем они, вероятно, будут применяться в обычных компьютерах.) Второй пример - разложение на множители и аналогичные теоретико-числовые задачи, связанные с абелевыми группами. В 1994 году П. Шор (P. Shor) придумал квантовый алгоритм4) <#"11" src="doc_zip161.jpg" />знаков за шагов ( ). Этот красивый результат может иметь скорее вредное, чем полезное применение: разлагая числа на множители, можно подбирать ключи к шифрам, подделывать электронные подписи и т.д. (Впрочем, трудности на пути создания квантового компьютера столь велики, что в течение ближайших 10 лет пользователи шифров могут спать спокойно.) Третий пример - это поиск нужной записи в неупорядоченной базе данных. Здесь выигрыш не столь значителен: для нахождения одной записи из требуется порядка операций на квантовом компьютере вместо операций на классическом. На этом список известных примеров заканчивается - не потому что квантовые компьютеры бесполезны для других задач, а потому что теория квантовых вычислений пока не разработана. Будем надеяться, что скоро появятся новые математические идеи, которые позволят придумать новые примеры.

Физическая реализация квантового компьютера - чрезвычайно интересная, но сложная задача. Еще несколько лет назад высказывались сомнения в ее принципиальной разрешимости. Дело в том, что любое унитарное преобразование можно реализовать лишь с некоторой точностью. Кроме того, систему спинов или аналогичную квантовую систему нельзя полностью защитить от возмущений со стороны окружающей среды. Все это должно приводить к погрешностям, которые будут накапливаться в процессе вычисления. Через шагов (где - точность каждого унитарного преобразования) вероятность ошибки станет порядка единицы. К счастью, эту трудность можно преодолеть, используя квантовые коды, исправляющие ошибки. В 1996 году П. Шор предложил схему коррекции ошибок в процессе квантового вычисления (fault-tolerant quantum computation), которая была вскоре усовершенствована. Окончательный результат состоит в следующем. Существует некоторое пороговое значение точности , такое что при возможно сколь угодно длинное квантовое вычисление. Однако при ошибки накапливаются быстрее, чем их удается исправлять. По разным оценкам, лежит в интервале от до (точное значение зависит от характера возмущений и используемой схемы коррекции ошибок).

Итак, принципиальных препятствий для реализации квантового компьютера нет. Однако задача столь трудна, что ее можно сравнить с задачей об управляемом термоядерном синтезе. В самом деле, необходимо удовлетворить нескольким почти несовместимым требованиям.

Элементы квантового компьютера - квантовые биты (спины или что-то подобное) - должны быть изолированы друг от друга и от окружающей среды.

Необходимо иметь возможность избирательного воздействия на пару квантовых битов. (Возможно, потребуется несколько типов воздействия на одну и ту же пару, описываемых различными унитарными операторами.)

Каждый из унитарных операторов должен быть реализован с точностью (см. выше).

Реализуемые операторы должны быть достаточно нетривиальны. Точнее говоря, они должны образовывать полный базис, чтобы любой другой оператор в определенном смысле выражался через них.

В настоящее время существует несколько подходов к проблеме реализации квантового компьютера.

Отдельные атомы или ионы. Это первая и наиболее хорошо разработанная идея, она существует в нескольких вариантах. Для представления квантового бита можно использовать как обычные электронные уровни, так и уровни тонкой и сверхтонкой структуры. Имеется экспериментальная техника, позволяющая удерживать отдельный ион или атом в ловушке из постоянного магнитного или переменного электрического поля в течение длительного времени (порядка 1 часа). Ион можно "охладить" (т.е. погасить колебательное движение) при помощи лазерного луча. Подбирая длительность и частоту лазерных импульсов, можно приготовить произвольную суперпозицию основного и возбужденного состояний. Таким образом, управлять отдельным ионом достаточно легко. В ловушку можно также поместить два или большее число ионов на расстоянии несколько микрон друг от друга и управлять каждым из них в отдельности. Однако организовать взаимодействие между ионами достаточно трудно. Для этой цели предложено использовать коллективные колебательные моды ионов (обычные механические колебания с частотой в несколько мегагерц). Другой способ (для нейтральных атомов): поместить атомы в отдельные электромагнитные резонаторы, связанные друг с другом (пока непонятно, как это реализовать технически). Наконец, третий способ: при помощи нескольких лазерных лучей можно создать периодический потенциал ("оптическую решетку"), удерживающий невозбужденные атомы. При этом возможна ситуация, когда возбужденные атомы могут свободно двигаться. Таким образом, возбуждая на короткое время один из атомов, мы заставляем его взаимодействовать с соседями. Это направление экспериментальной физики сейчас быстро развивается и, по-видимому, имеет большие перспективы.

Ядерный магнитный резонанс. В молекуле с несколькими различными ядерными спинами произвольное унитарное преобразование можно реализовать при помощи последовательности импульсов магнитного поля. Это было проверено экспериментально при комнатной температуре. Однако для приготовления начального состояния необходима температура < K. Помимо трудностей с охлаждением, при такой температуре возрастают нежелательные взаимодействия молекул друг с другом. Кроме того, непонятно, как избирательно воздействовать на данный спин, если в молекуле есть несколько одинаковых спинов.

Системы сверхпроводящих гранул. При сверхнизких температурах единственной степенью свободы микроскопической сверхпроводящей гранулы (диаметром в несколько сотен ангстрем) является ее заряд. Он может изменяться на величину, кратную двум зарядам электрона (поскольку электроны в сверхпроводнике связаны в пары). Меняя внешний электрический потенциал, можно добиться такой ситуации, когда два зарядовых состояния будут иметь почти одинаковую энергию. Эти два состояния можно использовать в качестве базисных состояний квантового бита. Гранулы взаимодействуют между собой посредством джозефсоновских контактов и взаимной электрической емкости. Этим взаимодействием можно управлять. Основная трудность состоит в том, что нужно управлять каждой гранулой в отдельности, причем с высокой точностью. По-видимому, этот подход перспективен, но для его реализации потребуется создание новой технологии.

Анионы. Анионы - это особые возбуждения в двумерных квантовых системах, в частности, в двумерной электронной жидкости в магнитном поле. Один из авторов (А.К.) считает этот подход наиболее интересным (поскольку он же его и придумал [32 <#"19" src="doc_zip177.jpg" />. Для этого, как правило, требуется контролировать параметры системы с еще большей точностью. Однако можно представить ситуацию, когда высокая точность достигается автоматически, т.е. исправление ошибок происходит на физическом уровне. Примером являются двумерные системы с анионными возбуждениями.

Все частицы в трехмерном пространстве являются либо бозонами, либо фермионами. Волновая функция бозонов не меняется при перестановке двух частиц, а волновая функция фермионов умножается на . В любом случае при возвращении каждой из частиц на прежнее место состояние системы не меняется. В двумерных системах возможно более сложное поведение. Прежде всего заметим, что речь пойдет не об элементарных частицах типа электрона, а о возбуждениях, или дефектах в двумерной электронной жидкости. Такие возбуждения похожи на "настоящие" (т.е. элементарные) частицы, но обладают некоторыми необычными свойствами. Возбуждение может иметь дробный электрический заряд (например, от заряда электрона). При движении одного возбуждения вокруг другого состояние окружающей их электронной жидкости меняется строго определенным образом, зависящим от типа возбуждений и от топологии пути, но не от конкретной траектории. В простейшем случае волновая функция домножается на число ( для анионов в двумерной электронной жидкости в магнитном поле при факторе заполнения ). Возбуждения с таким свойством называются абелевыми анионами. Другой пример абелевых анионов описан (на математическом языке) в разделе 14.1 <#"22" src="doc_zip182.jpg" />.) При наличии нескольких неабелевых анионов состояние электронной жидкости является вырожденным, причем кратность вырождения экспоненциально зависит от числа анионов. Другими словами, существует не одно, а много состояний, которые могут образовывать произвольные квантовые суперпозиции. На такую суперпозицию нельзя никак воздействовать, не перемещая анионы, поэтому она идеально защищена от возмущений. Если обвести один анион вокруг другого, суперпозиция подвергнется определенному унитарному преобразованию. Это преобразование является абсолютно точным. (Ошибка может возникнуть, только если анион "вырвется у нас из рук" вследствие квантового туннелирования).

На первый взгляд, проект с использованием анионов выглядит наименее реалистично. Прежде всего, абелевы анионы не годятся для квантовых вычислений, а неабелевы еще только предстоит найти в эксперименте. Для реализации квантового компьютера нужно контролировать каждую из частиц, которые будут двигаться на расстояниях порядка долей микрона друг от друга. Это чрезвычайно сложная техническая задача. Однако, с учетом высоких требований к точности, осуществить любой из перечисленных выше подходов ничуть не легче. Кроме того, идея топологического квантового вычисления, лежащая в основе подхода с анионами, может воплотиться каким-либо другим способом. Например, защищенная от возмущений квантовая степень свободы может возникнуть на конце "квантовой проволоки" (одномерного проводника с нечетным числом распространяющихся электронных мод, находящегося в контакте с трехмерным сверхповодником).

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

Раздел №1. Алгоритм

Тема 1.1 Что такое алгоритм?

Неформально алгоритм - это однозначно определенная совокупность инструкций по преобразованию исходных данных в результат, причем все инструкции элементарны, т.е. при их выполнении "нам придется только механически следовать предписаниям, как если бы мы были роботами: от нас не потребуется ни понимания, ни искусства, ни изобретательности" [5, с. 270] <#"10" src="doc_zip184.jpg" />результат,

Что такое "входные данные" и "результат"? Рассмотрим, например, задачу об умножении двух многочленов с целыми коэффициентами. Тогда входные данные - это пара многочленов. Проблема в том, как записать эти многочлены, чтобы их можно было ввести в компьютер. Машины Тьюринга, которые мы рассматриваем ниже, понимают лишь конечные последовательности символов (слова) из некоторого конечного множества , называемого внешним алфавитом. Поэтому строгая формулировка вычислительной задачи должна включать в себя алфавит и способ кодировки входных данных. Например, можно записать пару многочленов с использованием 10 цифр, символа переменной , знаков +, -, * и скобок: (x**2-5)(-4*x+1). В другой кодировке коэффициенты записываются в двоичной системе счисления и перечисляются через запятую; два многочлена разделяются звездочкой: 1, 0, -101* -100, 1. Таким образом, мы имеем две различные вычислительные задачи. С практической точки зрения, обе задачи эквивалентны, поскольку перевод из одной кодировки в другую осуществляется с помощью полиномиального алгоритма. Пока определения полиномального алгоритма у нас нет, давайте будем формалистами: вычислительная задача - это частичная1) <#"16" src="doc_zip187.jpg" />(где обозначает множество конечных слов в алфавите ). Потом мы позволим себе некоторую вольность и будем говорить о задаче умножения многочленов или разложения целого числа на множители, имея ввиду, что все разумные кодировки эквивалентны (т.е. переводятся друг в друга при помощи полиномиальных алгоритмов). Однако нужно помнить, что не всякая кодировка является "разумной". Нехорошо, например, представлять натуральное число набором из звездочек, потому что длина такой записи экспоненциально велика по сравнению с двоичной или десятичной записью. Заметим также, что в некоторых задачах нет хорошего выбора "разумной" кодировки, в таких случаях (они нам не встретятся) необходимо указывать кодировку всякий раз, когда формулируется задача.

Теперь дадим формальное определение алгоритма.

Машины Тьюринга.

Машина Тьюринга (сокращенно МТ) однозначно задается указанием набора , где , , - конечные множества, причем ; - некоторый элемент ; - некоторый элемент , а - некоторая (частичная, вообще говоря) функция из в .

Составляющие части МТ называются так:

- алфавит,

- пустой символ (или пробел),

- внешний алфавит,

- множество состояний управляющего устройства,

- начальное состояние,

- функция переходов.

Состояние МТ задается тройкой , где - бесконечное слово в алфавите , т.е. произвольная последовательность элементов ; - неотрицательное целое число; . Символы слова будем, как это принято, представлять записанными на ленте, разбитой на ячейки, по ячейке на символ. На ленте также имеется головка, которая расположена над ячейкой с номером . Наглядно это изображается так:

Рисунок 1.1: Лента, разбитая на ячейки

Помимо ленты машина Тьюринга имеет управляющее устройство, состояние которого задается элементом множества .

Состояния МТ меняются дискретно. За один такт работы управляющее устройство выполняет следующие действия (полагаем, что МТ находится в состоянии ):

читает символ, находящийся под головкой (т.е. определяет );

вычисляет значение функции переходов: (если функция переходов на паре не определена, то останавливает машину Тьюринга);

записывает на ленту в ячейку символ , сдвигает головку на и переходит в состояние (другими словами, новое состояние машины задается тройкой );

если , то останавливает машину.

Пожалуй, всякий согласится, что эти действия не требуют ни понимания, ни искусства, ни изобретательности.

Работа машины Тьюринга будет всегда начинаться из состояния , где за конечным словом , состоящим из символов внешнего алфавита (множество таких слов обозначается ), следует бесконечное слово, целиком состоящее из пустых символов. Слово будем называть входом МТ. В любой момент времени слово, записанное на ленте, однозначно записывается в виде , где последний символ слова - не пустой, а за ним идут только пустые символы. Будем называть слово используемой частью ленты.

Выполняя один такт работы за другим, машина Тьюринга порождает последовательность состояний

Если МТ останавливается, используемая часть ленты в достигнутом перед остановкой состоянии называется результатом работы МТ.

Тема 1.2 Вычислимые функции и разрешимые предикаты

Каждая машина Тьюринга вычисляет частичную функцию из в , отображающую вход в результат работы МТ на входе при условии, что результат работы является словом во внешнем алфавите. Для входов, на которых машина не останавливается или результат содержит символы из , функция не определена. Из определения ясно, что любая МТ вычисляет ровно одну функцию (быть может, нигде не определенную).

Определение 1.1 Частичная функция из в называется вычислимой, если существует машина Тьюринга , для которой . При этом будем говорить, что вычислима на .

Не все функции вычислимы. Это ясно из сравнения мощности множества функций (континуум) и мощности множества машин Тьюринга (счетное множество). Более интересные примеры см. в задачах 1.3-1.5.

Под предикатом будем понимать некоторое условие, которое выполняется (предикат истинен) или не выполняется (предикат ложен) для каждого слова из . Определенные таким образом, предикаты легко отождествляются с языками (подмножествами слов в ) - предикату соответствует множество слов, на которых он истинен. Каждому предикату сопоставим характеристическую функцию, которая равна 1 на множестве слов, для которых предикат истинен, и равна 0 на множестве слов, для которых предикат ложен. Мы будем обозначать характеристическую функцию так же, как и сам предикат. Предикат разрешим, если его характеристическая функция вычислима. О машине Тьюринга, вычисляющей характеристическую функцию предиката, будем говорить, что она дает ответ ("да" или "нет") на вопрос "истинно ли значение предиката на входе ?"

Понятия вычислимой функции и разрешимого предиката будут использоваться и для функций (предикатов) от многих переменных.

Пусть - некоторый алфавит, а - натуральное число. Пусть - машина Тьюринга с внешним алфавитом . Построим частичную функцию из в так: , если результат работы машины на входе совпадает со словом . Если машина не останавливается или на ленте записано что-нибудь не то (например, символы не из алфавита и т.п.), то не определена.

Определение 1.2. Частичная функция из в называется вычислимой, если существует машина Тьюринга , для которой .

Предикат от нескольких переменных разрешим, если его характеристическая функция вычислима.

Нас будут интересовать ресурсы, требующиеся для вычислений. Два важнейших ресурса - время и память. Будем говорить, что машина Тьюринга работает за время , если максимальное (по всем входам длины ) количество тактов, которое проработает до остановки, равно . Аналогично, машина Тьюринга работает на памяти , если наиболее удаленное от начала ленты положение головки при вычислениях на входах длины равно .

Вычисления на машинах Тьюринга.

Очевидно, что МТ задает алгоритм в смысле приведенного выше неформального определения. Обратное утверждение называется тезисом Черча:

"любой алгоритм может быть реализован машиной Тьюринга"

Не вдаваясь в обсуждение тезиса Черча, заметим, что в настоящее время нет серьезных оснований подвергать его сомнению. Все известные в настоящее время алгоритмы реализуются машинами Тьюринга. Подробное изложение теории алгоритмов читатель может найти в книгах [<#"16" src="doc_zip285.jpg" />, которая, получая на вход пару , дает выход . Здесь через обозначено описание некоторой машины Тьюринга . Действительно, предположим, что тетрадь начинается со страниц, где записаны инструкции по работе. Тогда выполнять эти инструкции можно следующим образом: пометим текущую страницу; пролистаем тетрадь до начального раздела, содержащего инструкции; найдем нужную инструкцию; вернемся назад и выполним ее.

Сложностные классы.

Не для всякой вычислимой функции можно реально осуществить вычисление ее значения. Существование алгоритма не означает, что нам по силам проделать все предписанные действия. Препятствие может заключаться в том, что требуемые для этого вычисления ресурсы слишком велики. Поэтому нас интересует не столько существование алгоритма для решения задачи, сколько существование эффективного алгоритма.

Формализовать это понятие непросто. Принятый сейчас способ состоит в том, что выделяются классы тех функций или предикатов, вычисление которых возможно при задаваемых ограничениях на потребляемые ресурсы.Принадлежность функции тому или иному сложностному классу служит удобной характеристикой возможностей ее эффективного вычисления, не связанной с конкретными реализациями алгоритмов.

Наиболее важные классы получаются, если накладывать ограничения на рост времени работы и/или используемой памяти в зависимости от длины входного слова. А наиболее важное различие между эффективными и неэффективными вычислениями задается функциями полиномиального роста. Функция - полиномиального роста, если для некоторой константы при достаточно больших выполняется неравенство . В этом случае будем использовать обозначение .

Определение 1.3. Предикат на множестве принадлежит классу (и называется полиномиально вычислимым ), если его характеристическая функция вычислима на машине Тьюринга , для которой .

Определение 1.4. Предикат на множестве принадлежит классу , если его характеристическая функция вычислима на машине Тьюринга , для которой .

По аналогии с предикатами можно определить и функции, вычислимые за полиномиальное время, и функции, вычислимые на полиномиальной памяти. Для классов таких функций также используются обозначения и , так что точный смысл этих обозначений нужно восстанавливать из контекста.

Тема 1.3 Схемы

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

Схема вычисляет функцию , если для любых значений исходных переменных результатом вычисления является .

Схема называется формулой, если каждая вспомогательная переменная используется в правой части присваиваний только один раз. (Обычные математические формулы именно так задают последовательность присваиваний: "внутри" формул не принято использовать ссылки на их части или другие формулы.)

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

Базис называется полным, если для любой булевой функции есть схема в этом базисе, вычисляющая . Ясно, что в полном базисе можно вычислить произвольную функцию (такую функцию можно представить как упорядоченный набор из булевых функций).

Булева функция может быть задана таблицей значений. Приведем таблицы значений для трех функций

( отрицание, дизъюнкция, конъюнкция ), образующих полный базис, который будем считать стандартным. В дальнейшем имеются в виду схемы именно в этом базисе, если явно не указано что-либо иное.

Конъюнкция и дизъюнкция определяются для произвольного числа булевых переменных аналогичным образом: конъюнкция равна 1 только тогда, когда все аргументы равны 1, а дизъюнкция равна 0 только тогда, когда все аргументы равны 0. В стандартном базисе они очевидным образом вычисляются схемами (и даже формулами) размера .

Теорема 1.1. Базис - полный.

Доказательство. Литералом будем называть переменную или ее отрицание. Конъюнкцией литералов (это схема и даже формула) легко представить функцию , которая принимает значение 1 ровно один раз: при . Если , включаем в конъюнкцию переменную , если , то включаем в конъюнкцию . Произвольная функция может быть представлена в виде

(1.1)

В таком случае говорят, что представлена в дизъюнктивной нормальной форме (ДНФ), т.е. как дизъюнкция конъюнкций литералов1) <#"16" src="doc_zip351.jpg" />, вычисляющей функцию , называется схемной сложностью функции в базисе и обозначается . Переход от одного полного конечного базиса к другому полному конечному базису меняет схемную сложность функций на множитель . Так что в асимптотических оценках выбор конкретного полного базиса неважен и поэтому будем использовать обозначение для схемной сложности в конечном полном базисе.

Каждый предикат на множестве определяет последовательность булевых функций следующим образом: , где справа стоит характеристическая функция предиката .

Определение 1.5. Предикат принадлежит классу , если .

Теорема 1.2. .

Если МТ работает за полиномиальное время, то и память, которую она использует, ограничена полиномом. Поэтому весь процесс вычисления на входном слове длины можно представить таблицей вычисления размера , где , .

Рисунок 1.2: Процесс вычисления

Строка с номером таблицы задает состояние МТ после тактов работы. Символы , записанные в таблице, принадлежат алфавиту . Символ определяет пару (символ, записанный в -й ячейке после тактов работы; состояние управляющего устройства после тактов работы, если головка находится над -й ячейкой, в противном случае второй элемент пары - ). Для простоты также считаем, что если вычисление заканчивается при некотором входе за тактов, то строки c номерами, большими , повторяют строку с номером .

Построить схему, вычисляющую значения предиката на словах длины , можно следующим образом. Состояние каждой клетки таблицы можно закодировать конечным (не зависящим от ) числом булевых переменных. Имеются локальные правила согласования, т.е. состояние каждой клетки в строке ниже нулевой однозначно определяется состояниями клеток в предыдущей строке, лежащих непосредственно над данной ( ), левее данной ( ) и правее данной ( ). Каждая переменная, кодирующая состояние клетки , есть функция от переменных, кодирующих состояния клеток , , . Все эти функции могут быть вычислены схемами конечного размера. Объединяя эти схемы, получим схему, вычисляющую все переменные, кодирующие состояния клеток таблицы; размер этой схемы будет .

Осталось заметить, что переменные, кодирующие часть клеток нулевой строки, определяются входным словом, а переменные, кодирующие остальные клетки нулевой строки, являются константами. Чтобы узнать результат вычисления, нужно определить символ, записанный в нулевой ячейке ленты в конце вычисления. Без ограничения общности можно считать, что состояния клеток таблицы кодируются так, что одна из кодирующих переменных равна 1 только в том случае, когда в ячейке записана 1. Тогда значение этой переменной для кода и будет результатом вычисления.

Замечание 1.1. Класс шире класса . Любой функции от натурального аргумента со значениями в можно сопоставить предикат по правилу , где обозначает длину слова . Ограничение такого предиката на слова длины тождественно равно 0 или 1 (в зависимости от ). Схемная сложность таких функций ограничена константой. Поэтому все такие предикаты по определению принадлежат P/poly, хотя среди них есть и неразрешимые предикаты.

Справедливо следующее усиление теоремы.

Теорема 1.3. принадлежит тогда и только тогда, когда

существует МТ, которая по числу за время строит схему вычисления .

Доказательство. Данное в доказательстве теоремы 1.2. описание нетрудно превратить в МТ, которая строит схему вычисления за полиномиальное по время (схема имеет простую структуру: каждая переменная связана с предыдущими одними и теми же правилами согласования).

Столь же просто. Вычисляем размер входного слова. Затем строим по этому размеру схему вычисления , используя указанную в условии 2 машину. После этого вычисляем на машине, которая по описанию схемы и значениям входных переменных вычисляет значение схемы за полиномиальное от длины входа время.

Задачи

Постройте машину Тьюринга, которая записывает входное двоичное слово в обратном порядке.

Постройте машину Тьюринга, которая складывает два числа, записанные в двоичной системе. Для определенности считайте, что записи чисел разделены специальным символом алфавита " ".

Докажите, что не существует алгоритма, который по машине Тьюринга и входу определяет, остановится ли она на этом входе.

Докажите, что не существует алгоритма, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте.

Пусть - максимальное время, которое может пройти до остановки машины Тьюринга с состояниями и символами алфавита, если ее запустить на пустой ленте. Докажите, что функция растет быстрее любой вычислимой всюду определенной функции , то есть .

Набор элементарных инструкций у описанных выше машин Тьюринга крайне беден. Имеются разнообразные их обобщения, например, многоленточные машины Тьюринга. В отличие от описанной выше, такая МТ имеет несколько (конечное множество) лент, каждая со своей головкой, управляющему устройству доступны символы, находящиеся в ячейках, на которых расположены головки лент. Выделены две ленты: входная, с которой разрешается только читать символы, и выходная, на которую разрешается только писать символы. Остальные ленты называются рабочими. Многоленточная машина называется -ленточной, если у нее рабочих лент. Действие за такт работы состоит в изменении состояния управляющего устройства, изменении символов в ячейках под головками и изменении положений головок на лентах (каждая головка сдвигается не более, чем на одну позицию). Это действие однозначно определяется состоянием управляющего устройства и набором символов в ячейках под головками. Если действие выполнить нельзя, машина останавливается.

В начале работы многоленточной машины Тьюринга все ленты пусты, кроме входной, на которой записан вход. Результат работы машины - состояние выходной ленты в конце работы.

Если интересоваться сложностью алгоритмов с точностью до полиномиально ограниченного множителя, многоленточные машины ничего не добавляют по сравнению с описанными выше машинами с единственной лентой.

Докажите, что двухленточную машину Тьюринга, работающую за время на входах длины , можно моделировать на машине с единственной лентой за время .

Докажите, что трехленточную машину Тьюринга, работающую за время на входах длины , можно моделировать на двухленточной за время .

Пусть - машина Тьюринга с единственной лентой, которая копирует входное слово (приписывая его копию справа от самого слова). Пусть - максимальное время ее работы на входах длины . Докажите, что для некоторого и для всех . Что можно сказать про , которое есть минимальное время ее работы на входах длины ?

Рассмотрим язык программирования, в котором есть всего натуральных переменных, разрешенные операции - прибавление и вычитание , разрешенная проверка - не равна ли переменная нулю. Разрешено использовать if-then-else и while, но рекурсия не разрешена. Докажите, что с помощью программ на таком языке программирования можно вычислять любую вычислимую функцию.

Постройте алгоритм, определяющий, является ли данный базис полным. Базисные функции заданы таблицами значений.

Пусть есть максимум сложности по всем булевым функциям от переменных. Докажите, что при достаточно больших .

Глубиной схемы называется максимальное число элементов на пути от входов к выходу. Покажите, что любую функцию можно вычислить схемой глубины не более из элементов и из элементов и с произвольным числом входов.

Докажите, что если из схемы глубины , вычисляющей функцию , выбросить все несущественные присваивания, то полученная схема имеет полиномиальный по размер.

Постройте схему, которая сравнивает два -битовых числа и имеет размер , а глубину .

Постройте схему сложения двух -битовых чисел размера .

Тот же вопрос, если дополнительно потребовать, чтобы глубина схемы была .

Функция равна 1 на двоичных словах, в которых число единиц больше числа нулей, и 0 - на остальных словах. Постройте схему, вычисляющую эту функцию, размер схемы должен быть линеен по , глубина - .

Постройте схему размера и глубины , которая проверяет, связаны ли путем две вершины в графе. Граф на вершинах, которые помечены числами от 1 до , задается булевыми переменными. Переменная , где , определяет, есть ли в графе ребро, соединяющее вершины и .

Пусть схема глубины из элементов и из элементов и с произвольным числом входов вычисляет сложение битов по модулю (функция ). Покажите, что размер схемы не меньше для некоторого .

Пусть - последовательность булевых функций от аргументов. Покажите, что следующие два свойства равносильны:

существует последовательность вычисляющих эти функции формул, размер которых не превосходит полинома от ;

существует последовательность вычисляющих эти функции схем глубины из элементов , и (с двумя входами).

Докажите, что существует разрешимый предикат, который принадлежит , но не принадлежит .

Раздел №2. Класс NP: сводимость и полнота

Тема 2.1 Класс NP

Термин "недетерминированный" неудачный, но он уже стал стандартным.

Класс NP определен только для предикатов. Говорят, например, что "свойство графа "иметь гамильтонов цикл1) <#"16" src="doc_zip497.jpg" />принадлежит классу , если существуют НМТ и полином такие, что

существует путь вычисления, дающий ответ "да" за время, не превосходящее ;

(1 вариант определения ) нет указанного выше пути; (2 вариант определения ) на любом пути вычисления ответа "да" не получается.

Замечание 2.1. Приведенные варианты определения эквивалентны. Чтобы исключить возможность ответов "да" на длинных путях вычисления, достаточно взять НМТ, имитирующую исходную НМТ и подсчитывающую количество сделанных исходной НМТ шагов. Когда число шагов превышает , машина останавливается.

Замечание 2.2. В предыдущем рассуждении допущена одна тонкая ошибка. В определении ничего не сказано о полиноме , кроме факта его существования. Если коэффициенты полинома невычислимы, могут возникнуть проблемы с указанным выше способом сведения одного определения к другому (нужно вычислить значение полинома). Чтобы в дальнейшем избегать этой сложности, будем считать, что полином имеет целые коэффициенты.

Замечание 2.3. Непосредственно из определения 2.1 следует, что . Является ли это включение строгим? Довольно интенсивные, хотя и безуспешные, попытки ответить на этот вопрос продолжаются уже почти 30 лет. Недавно С.Смейл включил проблему в число трех важнейших математических проблем следующего столетия (две другие - гипотеза Римана и гипотеза Пуанкаре).

Второе определение класса NP представляется более естественным. Оно использует понятие полиномиально вычислимого предиката от двух переменных. Определение такого предиката получается комбинацией определений 1.2 и 1.3. Под размером входа для предиката можно понимать также или , или - получатся эквивалентные определения.

Определение 2.2. Предикат принадлежит классу NP, если он представим в форме , где - полином, а .

Пример 2.1. Пусть " есть гамильтонов цикл в графе ". Более точно нужно сказать так: " есть двоичный код некоторого графа, а - код гамильтонова цикла в этом графе (используем такое кодирование, при котором код цикла не длиннее кода графа), такие что ". Возьмем . Тогда будет в точности означать, что в графе найдется гамильтонов цикл.

Теорема 2.1. Определения 2.1 и 2.2 эквивалентны.

Опр. 2.1 опр. 2.2. Пусть есть НМТ и полином из первого определения. Рассмотрим предикат " есть протокол работы на возможном пути вычисления со входом дающего ответ "да" за время, не превосходящее ." Длина такого протокола при разумном кодировании линейно зависит от времени вычисления (если использовать в качестве протокола описанную в доказательстве теоремы 1.2 таблицу вычисления, то квадратично), поэтому в качестве для второго определения можно взять ( ), умноженный на подходящую константу.

Чтобы закончить доказательство в этом случае, осталось проверить, что . Это почти очевидно. Мы должны проверить протокол некоторой НМТ, работающей за полиномиальное время. Это займет нас примерно на то же время (совершенно незачем смотреть на одну ячейку экспоненциально долго).

Опр. 2.2 опр. 2.1. Пусть есть из определения 2.2. Построим для определения 2.1. Она работает в два этапа.

Вначале недетерминированно пишет (который в силу определения 2.2 существует для любого слова , для которого ). Говорят еще, что "отгадывает" ("guesses") . Более точно это означает, что находит правый конец входного слова, сдвигается еще на одну ячейку вправо, записывает в нее , еще раз сдвигается вправо и переходит в такое недетерминированное состояние, в котором она пишет один из символов на ленту, сдвигается вправо и выбирает между сохранением этого состояния и переходом в (уже детерминированное) состояние начала следующего этапа.

После завершения первого этапа на ленте, помимо входного слова , записано еще и слово . Теперь осталось вычислить значение предиката за полиномиальное время. Это можно сделать, используя детерминированный алгоритм, существующий в силу определения 2.2.

Еще одно определение класса NP есть не более чем вариант определения 2.2, но именно в такой форме его удобно обобщать и получать определения других сложностных классов.

Определение 2.3. Имеются два персонажа: король A rthur (Артур), умственные способности которого полиномиально ограничены, и волшебник M erlin (Мерлин), который интеллектуально всемогущ и знает правильные ответы на все вопросы. Король A интересуется некоторым свойством (например, "есть ли у графа гамильтонов цикл"), а волшебник M хочет, чтобы король признал наличие этого свойства (ну, скажем, граф стремится к званию гамильтонова и дал M взятку). A не доверяет своему волшебнику, зная его корыстолюбие, и хочет иметь возможность самостоятельно проверить предложенный M ответ.

Поэтому они действуют следующим образом. A и M оба смотрят на слово , после чего M сообщает некоторую информацию (слово ), которая должна убедить A, что . Используя эту информацию, A проверяет убедительность аргументов M некоторым полиномиальным способом.

В этих терминах определение класса NP можно сформулировать так: свойство принадлежит классу NP, если у Артура есть полиномиальный способ проверять убедительность доводов Мерлина, причем:

у M есть способ убедить A в этом;

как бы M ни изощрялся, A не поверит, что .

Эквивалентность этого определения определению 2.2 не вызывает сомнений. Действительно, из-за полиномиальной ограниченности короля A, сообщение волшебника M должно иметь полиномиальный размер. В остальном различия между определениями чисто внешние.

Тема 2.2 Сводимость и NP-полнота

Сложность вычисления предикатов можно сравнивать, пользуясь следующим определением.

Определение 2.4. Сводимость по Карпу. Предикат сводится к предикату (обозначение ), если существует такая функция , что .

Сводимость по Карпу также называют полиномиальной сводимостью, а часто - просто сводимостью.

Лемма 2.1. Пусть . Тогда

.

Доказательство. Пункт 1 совершенно очевиден - чтобы вычислить значение предиката , достаточно применить ко входу функцию , а к результату ее работы - программу вычисления .

Пункт 2 следует из пункта 1.

Пункт 3 также прост. Его можно объяснять по-разному. Например, так: Мерлин сообщает Артуру (длина которого ограничена некоторым полиномом от длины , поскольку ) и слово , которое убеждает Артура в том, что . Артур также может проверить, что ему действительно сообщено . Используя определение 2.2, можно написать цепочку эквивалентностей

Полином в последнем выражении - это композиция полиномов и .

Определение 2.5. Предикат называется NP- полным, если любой предикат из к нему сводится.

Если некоторый NP-полный предикат можно вычислять за время , то любой предикат из NP можно вычислять за время для некоторого фиксированного числа . Такая потеря эффективности считается в этой науке несущественной.полные предикаты существуют, приведем примеры.

Выполнимость. Задается предикатом

есть формула с булевыми переменными и символами , которая истинна при некоторых значениях переменных.

Теорема 2.2 (Кук, Левин). 1) ; 2) - NP- полна.

Если , то .

Доказательство (теоремы 2.2). 1) Мерлину достаточно сообщить Артуру значения переменных, входящих в формулу, при которых она истинна. Артур справится с проверкой истинности полученного высказывания.

) Пусть предикат из NP, который нужно свести к , имеет вид .

Рассмотрим таблицу вычисления (см. доказательство теоремы 1.2) для МТ, вычисляющей (входом является пара ). Будем использовать те же переменные, что и в доказательстве теоремы 1.2 (коды состояний клеток таблицы вычисления). Чтобы таблица вычисления соответствовала правильно проведенному успешному (с ответом "да") вычислению, должны выполняться локальные правила согласования для каждой четверки клеток видаи результат должен быть "да". Каждое такое правило задается формулой от переменных, отвечающих либо рассматриваемой четверке, либо нулевой ячейке самой нижней строки таблицы. Определим формулу как конъюнкцию всех этих формул, в которые подставлены значения переменных, кодирующих вход , дополненный символами до длины . Значения, соответствующие и , - константы, поэтому переменные, от которых зависит эта формула, отвечают и кодам внутренних ячеек таблицы. Так что можно считать, что формула зависит от и еще от каких-то переменных, которые мы обозначим .

Итак, мы сопоставили слову формулу , которая по построению обладает следующим свойством. Если выполняется , то найдется такой набор значений , при котором истинна (эти значения описывают работу МТ на входе ). А если не выполняется, то всегда ложна (поскольку по сути утверждает, что вычисление на входе дает ответ "да"). Таким образом, при такая формула иногда (при некоторых значениях ) истинна, при - всегда ложна.

Другие примеры NP-полных задач получаются с помощью следующей леммы.

Лемма 2.2. Если и , то - NP-полная. И вообще, если - NP-полная, и , то - NP-полная.

Доказательство. Достаточно проверить транзитивность сводимости: если , , то . Она следует из того, что композиция двух полиномиально вычислимых функций полиномиально вычислима.

-КНФ. Задается предикатом

есть 3-КНФ, которая истинна истинна при некоторых значениях переменных. 3-КНФ - это конъюнкция дизъюнкций, каждая из которых содержит три литерала.

также NP-полна. Это устанавливается сведением к ней .

Теорема 2.3. .

Доказательство. Сопоставим любой схеме в стандартном базисе такую 3-КНФ, выполнимость которой равносильна тому, что вычисляемая схемой функция не равна тождественно 0. В эту КНФ будут входить все переменные схемы ( и - используем те же обозначения, что и в определении схемы). Для этого построим вначале конъюнкцию условий, означающих, что каждая из вспомогательных переменных имеет значение, соответствующее правой части присваивания . Есть три типа таких условий (они соответстуют трем базисным функциям), и каждый можно записать в виде 3-КНФ:

Подставляя эти 3-КНФ в , получим 3-КНФ . Искомая 3-КНФ имеет вид . Действительно, истинность равносильна утверждению: все присваивания выполнены правильно и в результате получилась 1 ( ). Значит, если при каких-то значениях переменных схема выдает 1, то выполнима, и наоборот.

Еще один простой пример сведения.

Задача ЦЛП (целочисленного линейного программирования). Дана система линейных неравенств с целыми коэффициентами. Есть ли у нее целочисленное решение? (Другими словами, совместна ли система?)

В этой задаче входом является матрица коэффициентов и вектор правых частей. То, что , не совсем очевидно. Оказывается, что в качестве подсказки Мерлин может сообщить Артуру значения переменных, при которых выполнены все неравенства системы. По определению, длина этого сообщения должна быть также полиномиально ограничена. Можно доказать, что из существования целочисленного решения следует существование целочисленного решения, размер записи которого ограничен полиномом от длины записи системы.

Сведем теперь 3-КНФ к ЦЛП. Построим по 3-КНФ систему линейных неравенств. Целочисленных переменных возьмем столько же, сколько есть булевых переменных. Булевой переменной сопоставим выражение . Отрицанию переменной сопоставим выражение . Каждой дизъюнкции ( - литералы) сопоставим неравенство , в котором , , - выражения, сопоставленные литералам дизъюнкции.

Искомая система содержит для всех неравенства , а также все неравенства, сопоставленные дизъюнкциям из КНФ. Очевидно, что выполнимость 3-КНФ равносильна совместности такой системы.

Замечание 2.4. Если не требовать целочисленности решений, то проверить совместность системы линейных неравенств можно за полиномиальное время.

Обширный список NP-полных задач содержится в книге Гэри и Джонсона [<#"16" src="doc_zip668.jpg" />. Спрашивается, есть ли -элементное множество вершин графа, любые две вершины которого соединены ребром.

Задачи

Докажите, что задача проверки выполнимости 2-КНФ (конъюнкции дизъюнкций, каждая из которых содержит два литерала) принадлежит P.

Докажите, что задача об эйлеровом пути в неориентированном графе (существует ли путь, проходящий по всем ребрам ровно по одному разу) принадлежит P.

Предположим, что класс NP совпадает с P. Докажите, что в этом случае за полиномиальное время можно не только проверить выполнимость формулы, но и найти значения переменных, при которых она истинна (аналогично для гамильтонова цикла и т.п.)

Докажите, что задача о паросочетаниях (есть мальчиков и девочек, известно, какие пары согласны друг с другом танцевать; надо определить, можно ли устроить танец, в котором все мальчиков и девочек соединены в пары) принадлежит NP и, более того, принадлежит P.

Постройте

полиномиальное сведение задачи 3-КНФ к задаче Клика;

тот же вопрос, но дополнительно требуется, чтобы количество решений сохранялось (если 3-КНФ при сведении соответствует пара (граф , размер ), то количество выполняющих наборов переменных для равно количеству клик размера в графе ).

Постройте

полиномиальное сведение задачи 3-КНФ к задаче 3-раскраска;

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

Покажите, что следующая задача является NP-полной: дан набор из не более чем типов квадратиков , на сторонах которых написаны какие-то буквы; дан список допустимых пар букв и список граничных букв; спрашивается, можно ли корректно сложить из квадратиков набора большой квадрат размера (так, чтобы на примыкающих сторонах квадратиков были только допустимые пары букв, а на границе квадрата - только граничные буквы).

Докажите, что предикат " - двоичная запись составного числа" принадлежит NP.

Докажите, что предикат " - двоичная запись простого числа" принадлежит NP.

Раздел №3. Вероятностные алгоритмы и класс BPP. Проверка простоты числа

Тема 3.1 Вероятностные алгоритмы

В вероятностных МТ (ВМТ), как и в недетерминированных, имеются состояния, из которых возможен переход в несколько (больше одного) состояний. Отличие состоит в том, что состояние, куда ВМТ делает переход, определяется результатом некоторого случайного процесса ("подбрасывания монеты"). Нужно оговорить, какие монеты допускаются. Например, если взять монету, вероятность выпадения герба для которой равна невычислимому числу, то возможности ВМТ, использующей подбрасывание такой монеты, будут больше, чем хотелось бы; она сможет вычислить и некоторые неразрешимые предикаты.

Обычно считают, что вероятности выпадения одинаковы для обеих сторон монеты, а результат подбрасывания отождествляется с числом 0 или 1.

Хотя для ВМТ нельзя сказать, какой в точности ответ она выдаст, можно определить вероятность того или иного ответа.

Определение 3.1. Предикат принадлежит классу BPP, если существуют такие ВМТ и полином , что машина заведомо остановится за время, не превосходящее , причем

с вероятностью большей дает ответ "да";

с вероятностью большей дает ответ "нет".

Если в этом определении заменить число на любое фиксированное число, большее , класс BPP не изменится. Есть простой способ добиться вероятности, сколь угодно близкой к 1. Возьмем несколько одинаковых машин, запустим их все, а окончательным результатом будем считать мнение большинства. Если вероятность правильного ответа для каждого экземпляра машины равна , то можно доказать, что вероятность правильного ответа после голосования машин не меньше , где .

Замечание 3.1. Представить физическую реализацию НМТ очень трудно (вспомним, что нам придется поместить в нее всезнайку Мерлина). А вероятностные машины вполне могут мыслиться как реальные устройства. Поэтому предикаты из класса BPP вполне можно считать реально вычислимыми.

Класс BPP можно определить и с помощью предикатов от двух переменных, как это было сделано для класса NP.

Определение 3.2. Предикат принадлежит классу BPP, если существуют такие полином и предикат , что

доля слов длины , для которых выполнено , больше ;

доля слов длины , для которых выполнено , меньше .

Теорема 3.1. Определения 3.1 и 3.2 эквивалентны.

Доказательство Опр. 3.1 Полагаем (количество подбрасываний монеты не превосходит общего числа действий). Определим предикат "машина на входе дает ответ "да" при указанной в последовательности результатов подбрасываний монеты". Этот предикат по очевидным причинам удовлетворяет определению 3.2.

Опр. 3.2 опр. 3.1. Случайно выбираем слово длины и подставляем в предикат, затем вычисляем значение предиката. Такая ВМТ удовлетворяет определению 3.1.

Определение 3.2 допускает следующее наглядное толкование. Отметим на плоскости точки из множества . Для рассмотрим сечение этого множества. Предикат , участвующий в определении 3.2, обладает таким странным свойством, что мера этого сечения при любом либо больше , либо меньше . Это разделяет значения на две категории: одна соответствует истинности предиката , другая - ложности.

Рисунок 3.1: Сечение множества

Классический пример задачи из BPP представляет проверка простоты числа: дано число , требуется определить, простое ли оно. Для этой задачи существует вероятностный алгоритм, работающий за полиномиальное время; он будет сейчас описан.

Необходимые сведения из теории чисел.

Подробное изложение элементарной теории чисел содержится в книге [<#"11" src="doc_zip740.jpg" />- простое и , то .

Китайская теорема об остатках. Пусть - разложение числа на взаимно простые множители. Тогда .

Другими словами, существует взаимно однозначное соответствие между остатками от деления на и парами остатков от деления на и на . {И это соответствие уважает операции сложения и умножения.)

Из малой теоремы Ферма следует, что позволяет утверждать, что - составное (говорят, что является свидетелем непростоты числа ). Это свидетельство косвенное - явного разложения на множители мы не получаем - и сильное: часто достаточно проверки при !

Однако проверки малой теоремы Ферма даже при всех может оказаться недостаточно. Алгоритм проверки будет использовать свидетелей еще одного типа: если , а , то - составное; и имеют общий делитель, больший 1. Поэтому свидетели такого вида (вообще говоря, гораздо более редко появляющиеся) позволяют сразу же указать разложение (против простоты которого они свидетельствуют) на два множителя за полиномиальное время (наибольший общий делитель двух чисел и можно найти за полиномиальное время, см. ниже).

Необходимые сведения из алгоритмической теории чисел.

Арифметические операции над числами можно выполнять за полиномиальное время от длины их записи (число записывается знаками). Например, схема умножения чисел , столбиком имеет размер , растущий квадратично от длины входа. Хотя квадрат от длины входа уже достаточно мал, чтобы быть полиномиальным, заметим, что для умножения -значных чисел есть и более экономные схемы размера .

В модулярной арифметике (арифметике остатков по модулю заданного числа ) можно вычислить по модулю схемой полиномиального размера от длины входа (в обычной арифметике даже результат возведения в степень может иметь экспоненциальный размер). Для этого нужно вычислить остатки от степеней последовательным возведением в квадрат и затем перемножить те из полученных чисел, которым соответствуют 1 в двоичной записи числа .

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

Существует также алгоритм проверки того, что из числа извлекается нацело корень -й степени. Это можно сделать, найдя достаточно точно приближенное значение корня и возведя ближайшее к нему целое число в -ю степень. Найти приближенное значение можно с помощью рекуррентной последовательности

если выбрать подходящее значение . Детали этого (полиномиального) алгоритма оставляются читателю для самостоятельного обдумывания.

Заметим, что все схемы, о которых шла речь выше, могут быть построены МТ за полиномиальное время. Так что все перечисленные задачи принадлежат классу P.

Тема 3.2 Алгоритм проверки простоты

Вход: число .

Шаг 1. Проверяем четность . Если , то ответ " - простое", если - четное и больше 2, то ответ " - составное", в противном случае переходим к шагу 2.

Шаг 2. Проверяем, извлекается ли из нацело корень -й степени при . Если извлекается, то ответ " - составное", иначе переходим к шагу 3.

Шаг 3. Записываем в виде , где , а - нечетное.

Шаг 4. Выбираем случайное среди чисел от до .

Шаг 5. Вычисляем по модулю .

Проверка 1. Если , то ответ " - составное".

Проверка 2. Если найдено такое , для которого , а , то ответ " - составное".

В противном случае ответ " - простое".

Анализ алгоритма.

Теорема 3.2. Если - простое, то описанный выше алгоритм всегда (с вероятностью 1) выдает ответ " - простое".

Если - составное, то ответ " - составное" будет получен с вероятностью .

Замечание 3.2. Чтобы получить полиномиальный вероятностный алгоритм проверки простоты числа в смысле определения 3.1, нужно дважды применить приведенный алгоритм. Тогда вероятность ошибки станет меньше .

Доказательство (теоремы 3.2). Из сказанного выше следует, что в доказательстве нуждается только второе утверждение.

Пусть , где (если такого представления нет, то на шаге 2 будет обнаружена непростота). Если , то проверка 1 для такого заведомо обнаружит, что - составное. Так что достаточно доказать, что не меньше половины тех , которые взаимно просты с , обнаруживают непростоту числа.

Обозначим группу через , группу - через . Из китайской теоремы об остатках следует, что группа изоморфна (изоморфизм задается естественным образом - вычислением остатков по модулю и по модулю ).

Рассмотрим множества , . Это подгруппы в и соответственно (произведение -х степеней есть -я степень, обратный к -й степени есть -я степень). Так что - целое число. Более того, отображение является гомоморфизмом групп, поэтому число прообразов при этом отображении одинаково для всех элементов . Очевидно, что (степеней квадратов не больше, чем всех степеней). Поэтому получаем пару невозрастающих цепочек множеств

Дальнейшее рассуждение разбивается на анализ нескольких случаев.

Пусть или .

Чтобы пройти проверку 1 в алгоритме, нужно после возведения в -ю степень получить пару остатков . Поскольку прообразов каждого числа из одинаковое количество, вероятность получения пары не выше .

Пусть .

Поскольку - нечетное, , т.е. найдется такое , , что , а или .

Будем доказывать, что с вероятностью не меньше в этом месте проверка 2 алгоритма обнаружит, что - составное. В данном случае , так что нужно понять, с какой вероятностью не равно . Рассмотрим два случая. Одно из множеств , равно . Пусть, например, . В этом случае можно утверждать, что (остатку при делении на соответствует пара остатков при делении на ).

Можно рассуждать так же, как и в случае 1. С вероятностью не меньше получим пару остатков , .

Оба множества содержат по крайней мере два элемента, пусть , . В этом случае может получиться как , так и , но вероятность этого не превосходит .

Замечание 3.3. Шаг 2 в алгоритме избыточен, дополнительными соображениями устанавливается, что и для чисел вида проверки 1, 2 дают правильный ответ со значительной вероятностью.и схемная сложность.

Теорема 3.3. .

Доказательство. Идея доказательства состоит в том, чтобы усилить оценки вероятностей с до . Число должно быть настолько мало, чтобы можно было выбрать такое случайное слово , при котором рассматриваемый предикат из BPP совпадает с .

Суть здесь в том, что повторение опытов за полиномиальное время экспоненциально уменьшает оценку вероятности ошибки , но не меняет размер входа . Поэтому можно добиться выполнения неравенства . При таком соотношении между и всегда найдется случайное слово, для которого нет ошибок ни при каких .

Действительно, вспомним наглядное толкование BPP, данное после теоремы 3.1. Если доля слов , на которых происходит ошибка, для каждого не превосходит , то доля тех слов , на которых происходит ошибка хотя бы для одного , не превосходит . Значит, найдутся и такие , на которых нет ошибок ни при каком .

Это типичное неконструктивное доказательство существования. Мы доказываем, что вероятность того, что объекта с нужными свойствами не существует, меньше 1. Но это и означает, что хотя бы один такой объект существует.

Раздел №4. Иерархия сложностных классов

Тема 4.1 Суть сложностных классов

Напомним, что мы отождествляем языки и предикаты, как описано в лекции 1 <#"16" src="doc_zip902.jpg" />означает .

Определение 4.1. Пусть - некоторый класс языков. Класс дополнений составляют дополнения ко всем языкам из . Формально

Непосредственно из определений классов следует, что , , .

Игры, в которые играют машины.

Рассмотрим игру, в которую играют два игрока, будем их называть белые (Б) и черные (Ч). Игрокам сообщается некоторое слово , и они делают ходы по очереди ( - первый ход белых, - первый ход черных и т.д.). Каждый ход может быть описан словом длины , где - некоторый полином. Игра завершается после некоторого, заранее заданного, числа ходов1) <#"22" src="doc_zip917.jpg" />, истинность которого означает, что выиграли белые (ничьих не бывает, так что ложность означает, что выиграли черные). Предикат зависит от исходного слова и ходов, сделанных игроками: - белыми, - черными. Поскольку замкнут относительно дополнений, предикат , утверждающий выигрыш черных, также принадлежит .

Отсутствие ничьих и конечность числа ходов гарантируют при заданном существование выигрышной стратегии либо для белых, либо для черных. (Формальное доказательство легко получается индукцией по числу ходов.) Поэтому каждой игре можно сопоставить два взаимно дополнительных множества

Многие сложностные классы можно определить как множества (или ), соответствующие тем или иным видам игр. Например, получаем следующие классы.

: множества (как и , впрочем) для игр, в которых никто не делает ходов.

: множества для игр, в которых белые делают 1 ход. Другими словами, это множества вида

: множества для игр, в которых белые делают 1 ход. Другими словами, это множества вида

: множества для игр из 2 ходов: 1 ход белых, 1 ход черных. Другими словами, это множества вида

Словами это можно сказать так: есть такой ход белых, что, как бы ни сыграли черные, белые выигрывают.

: множества для игр из 2 ходов. Другими словами, это множества вида

: множества для игр из ходов (в зависимости от четности последними ходят либо черные, либо белые). Другими словами, это множества вида

(если четное, то , , если нечетное, то , ).

: множества для игр из ходов (в зависимости от четности последними ходят либо черные, либо белые). Другими словами, это множества вида

(если четное, то , , если нечетное, то , ).

Классы и взаимно дополнительны: , .

Теорема 4.1 (Лаутеман [35 <#"18" src="doc_zip972.jpg" />.

Доказательство. Поскольку класс BPP замкнут относительно дополнений, достаточно показать, что .

Для этого нужно научиться формулировать свойство "множество содержит много элементов" с использованием кванторов существования и всеобщности. Мы сделаем это, предполагая, что рассматриваются подмножества некоторой конечной группы. Пусть - группа, а - подмножество . Свойство, которым мы будем отличать большие множества от малых, состоит в том, что некоторым количеством сдвигов множества можно покрыть всю группу

(4.1)

Чтобы выбрать подходящее значение , нужно найти случаи, когда (4.1) заведомо выполняется, и когда заведомо не выполняется.

Если

(4.2)

условие (4.1) заведомо ложно.

Условие (4.1) заведомо истинно, если для случайных независимых вероятность события больше 0. Другими словами, . Вероятность того, что случайный сдвиг не покрывает (не содержит) некоторый фиксированный элемент, равна по очевидным причинам . Вероятность того, что случайных сдвигов не покрывают фиксированный элемент, равна (покрытия разными сдвигами - независимые события). Поскольку покрывается элементов, вероятность события не больше (вероятность объединения событий не больше суммы вероятностей этих событий). Итак, при

(4.3)

условие (4.1) заведомо выполняется.

Рассмотрим теперь некоторый язык . Для него, как объяснялось выше, можно найти полиномиально вычислимый предикат и полином такие, что число , где , различает слова, принадлежащие языку (для них оно больше ), и слова, языку не принадлежащие (для таких слов это число меньше ). Параметр мы выберем позже, сейчас отметим, что его величина может быть экспоненциально мала, как объяснялось в лекции 3 <#"14" src="doc_zip1000.jpg" />длины так, чтобы произведение и обращение элемента в этой группе были полиномиально вычислимыми (например, в качестве групповой операции возьмем покомпонентное сложение по модулю два). Запишем следующее -условие

Другими словами, рассматриваем такую игру: белые своим ходом называют слов (элементов группы), а черные - один элемент, который, по их мнению, не покрыт сдвигами множества на слова , названные белыми.

Условие (4.2) в этом случае имеет вид , а условие (4.3): . Эти условия выполняются при подходящем выборе параметров. Можно взять порядка и порядка .

Замечание 4.1. Имеется рассуждение, которое "показывает", что время вычисления функций из класса BPP можно сделать, по-видимому, меньше для любого . Идея состоит в том, чтобы использовать генераторы псевдослучайных чисел. Такой генератор по набору битов длины строит набор длины , где . Если при этом выбирать короткие наборы случайно, то длинные наборы будут распределены так, что вычислительное устройство с ограниченными ресурсами (например, полиномиальная машина Тьюринга) не сможет отличить их от по-настоящему случайных. Это пояснение заменяет точное определение псевдослучайного генератора, которое нам не понадобится.

Существуют ли псевдослучайные генераторы, неизвестно. Их заведомо нет, если . Но в этом случае .

Если же и есть псевдослучайные генераторы, то можно находить за указанное выше время значение функции , вычисляя значения предиката из опр. 3.2 только для псевдослучайных .

Остается "небольшой" дефект в этом рассуждении: оно не проходит при и отсутствии псевдослучайных генераторов. Такая ситуация считается маловероятной.

Тема 4.2 Класс PSPACE

Как уже говорилось, в этот класс попадают те функции, которые могут быть вычислены на МТ, использующей память, ограниченную полиномом от длины входного слова. Класс PSPACE также можно описать, используя игры.

Теорема 4.2. тогда и только тогда, когда существует такая игра с полиномиальным от длины входного слова числом ходов и полиномиально вычислимым результатом, что Б имеет выигрышную стратегию .

Доказательство Покажем, что язык, определяемый игрой, принадлежит . Пусть число ходов ограничено . Определим по индукции набор машин Тьюринга для . Каждая по заданному началу игры длины определяет наличие выигрышной стратегии у Б. Последней в этом ряду машине нужно просто вычислить предикат . Машина перебирает все возможные варианты -го хода и консультируется с по поводу окончательных результатов игры. Ее оценка игры составляется очень просто: если текущий ход у Б, то достаточно найти один ход, при котором гарантирует выигрышную стратегию для Б. Если текущий ход у Ч, то при всех вариантах должна обнаружить выигрышную стратегию для Б. Машина определяет наличие выигрышной стратегии для Б в самом начале игры и для ее работы нам нужно использовать всю последовательность машин . Но каждая из этих машин использует небольшую (полиномиально ограниченную) память, так что весь процесс потребует лишь полиномиально ограниченной памяти.

Пусть есть машина , распознающая вхождение слова в язык на полиномиальной памяти. Во-первых, заметим, что вычисление на памяти бессмысленно проводить дольше, чем время (все начнет повторяться после того, как мы исчерпаем все состояния нашей системы, а их не более чем , где - соответственно множество состояний управляющего устройства и алфавит рассматриваемой МТ). Поэтому можно считать без ограничения общности, что время работы машины ограничено , где .

Чтобы было проще описывать игру, потребуем, чтобы после завершения вычисления МТ сохраняла без изменений достигнутое состояние.

Игра заключается в следующем. Белые утверждают, что ответ на входном слове равен "да", а черные хотят это проверить. Белые своим первым ходом декларируют состояние машины (строка, записанная на ленте, положение читающей головки, состояние управляющего устройства) после тактов. Черные своим ходом выбирают один из промежутков: от начала до -го такта или от -го такта до конца. Белые декларируют состояние в середине этого промежутка. Далее все повторяется: Ч выбирает одну из половинок, Б декларирует состояние в середине выбранной половинки и т.д.

Игра заканчивается, когда длина промежутка становится равной 1. Результат определяется так: для обоих концов этого промежутка в процессе игры были названы состояния . Если состояние правого конца получается из состояния левого конца за один такт работы , то Б выиграли, иначе выиграли Ч.

Если ответ на слове действительно "да", то белым нужно все время говорить правду, это гарантирует им выигрыш.

Если ответ на слове - "нет", то при любом ходе белых на одном из промежутков (или на обоих) будет содержаться ошибка. Ч должен указывать каждый раз именно этот промежуток.

Задача 4.1. Докажите, что класс языков, распознаваемых недетерминированными машинами, работающими на памяти , содержится в классе языков, распознаваемых детерминированными машинами, работающими на памяти .

В качестве следствия теоремы 4.2 получаем включения всех определенных выше классов , в класс . Взаимное соотношение этих классов можно изобразить диаграммой включений, показанной ниже. На этой диаграмме от большего класса к меньшему можно пройти, двигаясь по стрелкам. Внизу располагается класс , отвечающий играм с 0 ходов, затем идут дополняющие друг друга классы, отвечающие играм с конечным числом ходов (для одного хода это NP и co-NP, для двух ходов - и и т.д.). Завершается эта диаграмма классом , который определяется произвольными играми с одним естественным условием - время игры должно быть полиномиально ограничено размером входного слова. Мы уже доказали все включения, изображенные на этой диаграмме. Ни про одно из включений, следующих из этой диаграммы, неизвестно, является ли оно строгим. Быть может, скажем, . С другой стороны, возможно и так, что , где обозначает (не рассматривавшийся нами) класс языков, вычислимых за экспоненциальное время . Впрочем, наиболее популярна гипотеза о том, что все включения, изображенные на диаграмме - строгие.

Рисунок 4.1: Схема PSPACE

Задача 4.2. Машина Тьюринга с оракулом - это МТ с дополнительной оракульной лентой, куда она (машина) может записывать слова, а затем за один такт работы проверять, принадлежит ли записанное на оракульной ленте слово языку . По двум сложностным классам и можно определить класс таких языков, которые распознаются машинами из класса с оракулами из .

Докажите, что .

В классе существуют полные задачи (относительно полиномиальной сводимости). Простейший вариант получается применением предыдущей теоремы.

Задача . Задается предикатом

есть истинная булева формула с кванторами (True Quantified Boolean Formula), т.е. формула вида

где , - некоторая логическая формула, а - либо , либо . По определению, , а

.

Теорема 4.3. -полна.

Доказательство. Построим сведение любого языка к задаче c TQBF. Для этого превратим МТ, вычисляющую результат игры (предикат ), в схему, а ходы игроков закодируем булевыми переменными. Тогда наличие выигрышной стратегии у белых задается условием

где обозначает результат вычисления по схеме.

Чтобы превратить в булеву формулу, добавим новые переменные (значение, вычисленное при -м присваивании в схеме) и заменим на формулу вида

где - размер схемы, - правая часть -го присваивания.

После этой подстановки получим квантифицированную булеву формулу, которая истинна в точности для .

Раздел №5. Квантовые вычисления

Тема 5.1 Квантовые вычисления

Как уже говорилось во введении, обычные компьютеры не используют всех возможностей, предоставляемых природой. В них выполняются преобразования на конечных множествах состояний (действия с 0 и 1), а в природе есть возможность делать унитарные преобразования, т.е. действовать на бесконечном множестве1) <#"22" src="doc_zip1117.jpg" />конечно и имеет мощность .

Квантовый компьютер работает с конечными наборами элементарных состояний, называемых q-битами. Каждый q-бит имеет два выделенных состояния (если считать q-биты спинами, то это состояния "спин вверх" и "спин вниз"). Указание выделенных состояний для каждого q-бита системы задает не все возможные состояния системы, а только базисные. Возможны также любые линейные комбинации базисных состояний с комплексными коэффициентами. Базисные состояния мы будем обозначать , где , или , где . Произвольное состояние системы может быть представлено в виде2) <#"47" src="doc_zip1123.jpg" />

Пространство состояний для такой системы - конечномерное (размерности ) пространство над полем комплексных чисел.

Состояния

Обычного компьютера

квантового компьютера

биты

q-биты

базисное:

произвольное:

Небольшое уточнение: если умножить вектор на фазовый множитель, , ( - вещественное), то получится физически неотличимое состояние. Таким образом, состояние квантового компьютера - это вектор единичной длины, заданный с точностью до фазового множителя.

Вычисление можно представлять как последовательность преобразований на множестве состояний системы. Опишем, какие преобразования возможны в классическом, а какие - в квантовом случае.

Классический случай:

Квантовый случай:

преобразования - это функции из в

преобразования - это унитарные операторы, то есть операторы, сохраняющие длину вектора .

Замечание. Все сказанное относится только к замкнутым системам. Реальный квантовый компьютер - это часть большой системы (Вселенной), взаимодействующая с остальным миром. Квантовые состояния и преобразования открытых систем будут рассмотрены в разделах 9-10.

Теперь нужно дать формальное определение квантового вычисления. Как и в классическом случае, можно определить квантовые машины Тьюринга или квантовые схемы. Мы выбираем второй подход, который удобнее по ряду причин.

Тема 5.2 Определения и обозначения

Пространство состояний системы из q-битов можно записать в виде тензорного произведения . Сомножители соответствуют пространству состояний одного q-бита.

Тензорное произведение двух пространств и , в которых фиксированы базисы и , можно определить как пространство с базисом из элементов . (В данном случае - это то же самое, что , т.е. просто пара векторов.) Размерность тензорного произведения равна (произведению размерностей сомножителей).

Такое определение неинвариантно, т.е. зависит от выбора базисов в перемножаемых пространствах. Можно дать инвариантное определение. Для этого рассмотрим вначале пространство (бесконечномерное) с базисом , где , - произвольные векторы из перемножаемых пространств. Тензорное произведение будет факторпространством этого пространства по подпространству, порожденному векторами вида

Другими словами, указанные векторы считаются равными 0.

Можно доказать, что данные определения эквивалентны.

В нашем случае имеется естественный выделенный базис (соответствующий выделенным состояниям): для - , а для - . Пространство с выделенным базисом обозначается через . Выделенный базис считается ортонормированным, это задает скалярное произведение на пространстве состояний. Коэффициенты разложения вектора по этому базису называются амплитудами. Их физический смысл состоит в том, что квадрат модуля амплитуды интерпретируется как вероятность обнаружить систему в данном базисном состоянии. Как и должно быть, суммарная вероятность всех состояний равна , поскольку длина вектора предполагается единичной. (Вероятности будут подробно обсуждаться позже; до некоторых пор мы будем заниматься линейной алгеброй - изучать унитарные операторы на пространстве ).

Мы будем использовать (и уже использовали) принятые в физике обозначения, относящиеся к векторам и скалярному произведению в гильбертовом пространстве (их ввел Дирак). Векторы обозначаются , скалярное произведение - . Если и , то . (Здесь и далее обозначает комплексное сопряжение.) В записи векторов скобки нужны лишь "для красоты" - они указывают на тип объекта и придают симметрию обозначениям (см. ниже). Вместо можно было бы написать просто , хотя это и не принято. Поэтому - и то, и другое обозначает вектор .

Скалярное произведение антилинейно по первому аргументу1) <#"49" src="doc_zip1174.jpg" />

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

Запись ( - линейный оператор) можно толковать двояко: либо как скалярное произведение вектора на вектор , либо как - на . Так появляется сопряженный оператор : по определению, (бра-вектор, соответствующий ) равен линейному функционалу . Из определения сразу следует, что

Унитарный оператор - это линейный оператор, сохраняющий скалярное произведение. Условие

эквивалентно тому, что (где - тождественный оператор).

Наше определение скалярного произведения в согласовано с тензорным произведением:

В дальнейшем будет использоваться тензорное произведение операторов. Оно действует в тензорном произведении пространств, на которых действуют сомножители, по правилу

Если операторы заданы в матричном виде в некотором базисе, т.е.

(легко понять, что - линейный оператор: ), то матричные элементы оператора имеют вид .

Вычисление состоит из преобразований, считаемых элементарными (выполняемых за единицу времени).

Элементарное преобразование в классическом случае: такая функция из в , которая зависит от небольшого (не зависящего от ) числа битов и изменяет также небольшое число битов.Элементарное преобразование в квантовом случае: тензорное произведение произвольного унитарного оператора, действующего на части сомножителей , где мало ( ), и тождественного оператора, действующего на остальных сомножителях.

Тензорное произведение некоторого оператора , действующего на множестве q-битов , и тождественного оператора, действующего на остальных q-битах, будем обозначать . (В частности, обозначает действие на первых q-битах.)

Пример 5.1. Приведем матрицу оператора , действующего в пространстве . Оператор действует на второй q-бит, на остальных q-битах действие тождественное. Базисные векторы расположены в лексикографическом порядке: от до .

С этого места начинается вычислительная сложность. Пусть , тогда - некоторая матрица , - матрица размерности , у которой по диагонали стоят блоки из матриц . Эта матрица представляет один элементарный шаг. Когда применяется несколько таких операторов к разным парам q-битов, результат будет выглядеть гораздо сложнее. Не видно способа определить этот результат, кроме прямого перемножения матриц. Поскольку размеры матриц экспоненциально велики, потребуется экспоненциальное время для их перемножения.

Заметим однако, что вычисление матричных элементов возможно на полиномиально ограниченной памяти. Пусть нужно найти матричный элемент оператора

Очевидно, что

(5.1)

(Здесь - строки длиной битов.) Для вычисления этой суммы достаточно -го регистра для хранения текущих значений , еще одного регистра для хранения частичной суммы и некоторого фиксированного количества регистров для вычисления промежуточных произведений.

Определение 5.1. Квантовая схема. Пусть - некоторое множество унитарных операторов (базис). Тогда квантовая схема в базисе - это последовательность , где - множества q-битов,

Оператор, реализуемый квантовой схемой. Это оператор , равный .

Это определение не очень хорошо, так как не учитывает возможность использования дополнительной памяти в процессе вычисления. Поэтому дадим еще одно определение.

Оператор , реализуемый схемой в расширенном смысле. Это такой оператор, что произведение

действующее на q-битов, , для любого вектора удовлетворяет условию .

Таким образом, мы "берем напрокат" дополнительную память, заполненную нулями, и должны возвратить ее в прежнем состоянии. Какой смысл имеет такое определение? Зачем нужно требовать, чтобы дополнительные q-биты вернулись в состояние ? На самом деле это условие чисто техническое, однако важно, чтобы вектор состояния в конце вычисления был разложим, т.е. имел вид (с произвольным ). Если это так, то первая подсистема находится в определенном состоянии , поэтому про вторую подсистему (дополнительную память) можно забыть. В противном случае, совместное состояние двух подсистем оказывается "запутанным" (entangled), поэтому первую подсистему нельзя отделить от второй.

Раздел №6. Соотношение между классическим и квантовым вычислением

Тема 6.1 Соотношение между классическим и квантовым вычислением

Классический объект, соответствующий унитарному оператору, - перестановка. Любой перестановке естественно сопоставляется унитарный оператор в пространстве , действующий по правилу .

Аналогично определению 5.1, можно определить обратимые классические схемы, реализующие перестановки.

Определение 6.1. Обратимая классическая схема. Пусть - некоторое множество перестановок вида (базис). Обратимая классическая схема в базисе - это последовательность перестановок , где - множества битов, .

Перестановка, реализуемая обратимой схемой. Это произведение перестановок .

Перестановка , реализуемая схемой в расширенном смысле. Это такая перестановка, что произведение перестановок

(действующее на битов, ) для любого удовлетворяет условию .

В каких случаях функцию, заданную булевой схемой, можно реализовать обратимой схемой? Обратимые схемы реализуют только перестановки. Преодолеть эту трудность можно так. Вместо вычисления функции будем вычислять функцию , заданную соотношением (здесь означает побитовое сложение по модулю 2). Тогда значение можно получить так: .

Чтобы можно было вычислять функции, заданные булевыми схемами в полном базисе, недостаточно взять базис для обратимых схем из перестановок на двух битах. Оказывается, что любая перестановка на двух битах является линейной функцией (при естественном отождествлении множества и поля из двух элементов ): , где , , , , , . Поэтому все функции, вычисляемые обратимыми схемами в базисе из перестановок на двух битах, являются линейными.

А вот перестановок на трех битах уже достаточно, чтобы реализовать любую функцию. При этом не обязательно использовать все перестановки, достаточно включить в базис лишь две функции - отрицание и элемент Тоффоли . При этом имеется в виду реализуемость в расширенном смысле, т.е. можно брать напрокат биты в состоянии 0 и возвращать их после окончания вычислений в том же состоянии.

Задача 6.1. Докажите для обратимых схем полноту базиса, состоящего из отрицания и элемента Тоффоли.

Лемма 6.1. Пусть функция реализуется булевой схемой размера в некотором базисе . Тогда можно реализовать функцию обратимой схемой размера в базисе { , состоящем из функций ( ), а также функции .

Замечание 6.1. Помимо "полезного" ответа схема, указанная в формулировке леммы, производит "мусор" .

Замечание 6.2. Содержательный смысл операции - обратимое копирование бита (если начальное значение равно ). В литературе эта операция обычно называется Controlled NOT по причинам, которые станут ясными из дальнейшего.

Замечание 6.3. Применяя функцию можно менять биты местами в записи. Обратите внимание, что для перестановок битов достаточно также иметь в базисе , так как

Доказательство. Возьмем схему, вычисляющую . Пусть входные переменные - это . Вспомогательные переменные схемы и биты результата - это ; в обратимой схеме сопоставим им дополнительные биты, имеющие в начальном состоянии значение 0.

Каждое присваивание в схеме имеет вид , , . В обратимой схеме аналогом присваивания будет действие перестановки , , т.е. .

Поскольку начальные значения дополнительных переменных были равны 0, их конечные значения будут такими же, как и в булевой схеме.

Осталось поменять местами биты, чтобы получить указанный в условии формат ответа.

Весь процесс вычисления удобно представить следующей схемой (над прямоугольниками подписано количество битов, внутри - их содержимое):

Лемма 6.2. (очистка мусора). В условиях леммы можно произвести вычисление функции обратимой схемой размера (с использованием дополнительных битов).

Доказательство. Для очистки мусора будет использована обратимость. Изобразим процесс вычисления схемой, аналогичной той, что приведена в доказательстве леммы 6.1.

Замечание 6.4. Обратимыми вычислениями заинтересовались при попытке ответить на вопрос, какая энергия необходима для вычислений (классических). Анализ показал, что потери энергии можно устремить к нулю для всех вычислительных операций, кроме необратимых. Когда производится необратимая операция (например, стирание бита), два различных логических значения ( и ) становятся одинаковыми ( ). Однако физические законы на микроуровне являются обратимыми, поэтому отличие между старыми состояниями ( и ) должно сохраниться в каких-то неконтролируемых физических степенях свободы. Это можно интерпретировать как возрастание беспорядка (энтропии), которое в конечном счете проявится в окружающей среде в виде тепла. Величина энергии, требуемой для стирания одного бита, очень мала ( ), но конечна. Потеря энергии из-за необратимого стирания информации при форматировании жесткого диска емкостью 1 Гб равна Дж, что примерно соответствует затратам энергии на сдвиг головки диска на половину диаметра атома водорода. Это на много порядков меньше реального перемещения головки при форматировании.

С другой стороны, если емкость дисков будет расти столь же быстро, как в настоящее время, то к концу XXIII века для форматирования жесткого диска потребуется энергия, соответствующая годовому излучению Солнца.

Лемма об очистке мусора показывает, что можно избежать таких потерь энергии, связанных с необратимостью вычислений.

Можно также показать, что любое вычисление, требующее памяти , можно реализовать обратимым образом с использованием памяти, не превышающей . Приведем набросок доказательства.

Поскольку задача TQBF PSPACE-полна, то достаточно вычислять на небольшой памяти значение формулы

(6.1)

при условии, что вычислима булевой схемой небольшого размера . Покажем, что в этом случае значение формулы 6.1 можно вычислить на памяти . Вычисление будет организовано рекурсивно, начиная с внутренних кванторов.

Чтобы вычислить , вычислим , занесем результат в одну дополнительную ячейку, затем вычислим и занесем результат в другую ячейку. После вычислим и результат занесем в третью ячейку. Чтобы убрать мусор, прокрутим все вычисления, кроме последнего шага, в обратном направлении.

Разобравшись аналогичным образом с формулой , приходим к такому выводу: добавление квантора по булевой переменной увеличивает требуемую память не более чем на константу битов.

В заключение сформулируем теорему о вычислении обратимых функций, которая является прямым обобщением леммы 6.2.

Теорема 6.1. Пусть и вычислимы булевыми схемами размеров . Тогда реализуется обратимой схемой размера .

Доказательство. Дается следующей схемой вычислений (для простоты не указаны биты, которые "берутся напрокат" при вычислении из леммы 6.2.

Раздел №7. Базисы для квантовых схем

Тема 7.1 Точная реализация

Как выбрать базис для вычислений в квантовых схемах? Унитарных операторов бесконечно много, поэтому либо полный базис должен содержать бесконечное количество элементов, либо мы должны ослабить условие точной реализуемости оператора схемой, заменив его на условие приближенной реализуемости. Мы рассмотрим обе возможности.

Точная реализация.

Теорема 7.1. Базис, содержащий все унитарные операторы, действующие на парах q-битов, позволяет реализовать любой унитарный оператор в расширенном смысле.

Для доказательства этой теоремы введем важный класс операторов: операторы с квантовым управлением.

Определение 7.1. Определим по оператору оператор с квантовым управляющим q-битом (первый сомножитель) следующими соотношениями:

(7.1)

Графически будем изображать оператор с квантовым управлением как показано на рисунке. Верхняя линия соответствует первому сомножителю, нижняя линия - второму. Направление стрелок соответствует направлению перемножения операторов (справа налево).

Нам потребуются также операторы с несколькими управляющими q-битами:

(7.2)

Пример 7.1. Пусть . Тогда , а (элемент Тоффоли).

Теперь построим элемент Тоффоли, используя преобразования двух q-битов. Для начала найдем пару операторов, удовлетворяющих следующему соотношению . Например, годится такая пара:

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

Унитарный оператор действует на этом пространстве так: . Можно доказать (см.[8, 11.12 <#"22" src="doc_zip1355.jpg" />, где - подгруппа фазовых сдвигов, а - группа поворотов в трехмерном пространстве (т.е. группа ортогональных преобразований с детерминантом, равным ).

При этом действии соответствует поворот вокруг оси на , соответствует поворот вокруг на , а соответствует поворот вокруг на .

На рис. рис. 7.1 <#"22" src="doc_zip1368.jpg" />, и . Последний - это управляемый двумя битами фазовый сдвиг (умножение на ). Проверим эту схему. Пусть на вход подается вектор , где , . Если , то к будет применен оператор , т.е. и в третьем q-бите переставляются. Если же хотя бы один из управляющих битов равен 0, то к будет применен тождественный оператор. Это и есть действие элемента Тоффоли.

Рисунок 7.1: Действие элемента Тоффоли

С помощью элемента Тоффоли можно реализовать любую перестановку базисных векторов (с использованием дополнительной памяти).

Покажем, как реализовать оператор для любого , действуя только на пары q-битов. Для этого также потребуется дополнительная память. Будем строить оператор , действующий в пространстве q-битов и удовлетворяющий условию

(Предостережение: это условие не означает, что .)

Существует обратимая схема размера , вычисляющая произведение входных битов (с мусором); графически она представлена на рис. рис. 7.2 <#"63" src="doc_zip1391.jpg" />

Рисунок 7.2: Схема P размера О(k)

На рис. 7.3 <#"16" src="doc_zip1392.jpg" />и оператора с одним управляющим q-битом построить оператор . Мы применяем схему , а затем - обратную схему , после чего все вспомогательные биты возвращаются в исходное состояние. В промежутке самой верхней линии соответствует бит со значением . Его мы и используем для управления оператором , действующим на самой нижней линии. Другим способом можно записать как .

Рисунок 7.3: Схема оператора

Действие можно описать так: на подпространстве, порожденном векторами и , действует оператор , а на ортогональном дополнении к этому подпространству - тождественный оператор. Наша следующая задача: реализовать оператор, который устроен так же, но нетривиальное действие осуществляется на подпространстве, натянутом на произвольную пару базисных векторов. Пусть мы хотим реализовать произвольный оператор в подпространстве, натянутом на базисные векторы и , где , , . Пусть - такая перестановка, что , . Тогда нужный нам оператор представляется в виде . (Напомним, что - оператор, соответствующий перестановке .)

Итак, на парах базисных векторов мы можем действовать произвольно. Пока все использованные схемы имели размер , так что построенные действия реализуются эффективно. Следующая часть неэффективна. Имеет место следующая лемма.

Лемма 7.1. Любая унитарная матрица в пространстве может быть представлена в виде произведения матриц вида

Заметим, что в нашем случае , так что получаем представление в виде произведения экспоненциального большого числа базисных операторов.

Тема 7.2 Приближенная реализация

Теперь перейдем к конечным базисам. В этом случае возможно только приближенное представление операторов произведениями базисных. Чтобы определить приближенную реализацию, нам потребуется норма на пространстве операторов.

На пространстве состояний есть норма . Она, как и любая норма, по определению удовлетворяет следующим условиям:

(7.3)

(7.4)

(7.5)

Введем теперь норму на пространстве операторов. Пусть - пространство с нормой. Пространство операторов, действующих на нем, можно представить как (изоморфизм задается матричным представлением ).

Определение 7.2. Норма оператора (так называемая операторная норма\, вообще говоря, есть и другие) равна

Заметим, что - наибольшее собственное число оператора .

Эта норма обладает всеми перечисленными выше свойствами нормы, а кроме того, еще несколькими специфическими:

(7.6)

(7.7)

(7.8)

Доказательства этих свойств нормы получаются непосредственно из определения и оставляются в качестве упражнения.

Дадим теперь определение приближенной реализуемости. Если искомый оператор - , то его приближенная реализация будет обозначаться .

Определение 7.3. Оператор представляет оператор с точностью , если .

У этого определения есть два замечательных свойства. Во-первых, если мы имеем произведение нескольких операторов , каждый из которых имеет свое приближение с точностью , то произведение этих приближений приближает с точностью ( ошибки накапливаются линейно ):

Достаточно рассмотреть пример с двумя операторами:

В этой выкладке последнее равенство справедливо благодаря унитарности операторов. (Если рассматривать неунитарные операторы, то ошибки приближения могут накапливаться гораздо быстрее, например, экспоненциально.)

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

Второе свойство понятия " представляет с точностью " мы сформулируем в более общем контексте.

Определение 7.4. Оператор приближается в расширенном смысле оператором с точностью , если для любого из выполнено

(7.9)

Сформулируем это определение еще одним способом. Введем оператор , который действует по правилу . Оператор не унитарный, но изометричный. Условие из последнего определения можно переписать так

(7.10)

Рассуждение про накопление ошибок проходит и в этом случае (что, конечно, следует проверить).

Справедливо следующее утверждение: если приближает (в расширенном смысле) с точностью , то приближает с той же точностью . Это следует из того, что для унитарных операторов . Умножая выражение под нормой в (7.10) слева на , а справа - на , получим следствие из неравенства (7.10): .

Определение 7.5. Будем называть базис полным, если любой унитарный оператор можно с любой точностью представить в расширенном смысле квантовой схемой в базисе .

Теорема 7.2. (см. [<#"22" src="doc_zip1477.jpg" />, где

является полным. (Такой базис будем называть стандартным.)

Доказательство этой теоремы следует из решения задач 7.5-7.9.

Замечание 7.2. Если убрать из базиса квантовый элемент Тоффоли, он перестает быть полным. Однако многие важные вычисления можно делать и в таком усеченном базисе. В частности, как будет видно в дальнейшем, схемы, исправляющие ошибки, можно реализовать без элемента Тоффоли.

Можно оценить сложность реализации оператора в этом базисе. Если , то можно реализовать этот оператор с точностью квантовой схемой в базисе размера . Если матричные элементы заданы в двоичной записи, то эта схема строится по с помощью некоторого алгоритма примерно за то же время (множители и степени полинома могут отличаться). Идея построения такого алгоритма легко усматривается из задач 7.1 и 7.11.

Задачи

Докажите, что все операторы на одном q-бите в сочетании с оператором образуют полный базис. Решение должно быть достаточно эффективным: должен существовать алгоритм, который строит схему, реализующую произвольный оператор на q-битах, за время .

Докажите свойства операторной нормы(7.6-7.8).

Пусть операторы приближают в расширенном смысле операторы с точностью , . Докажите, что оператор приближает в расширенном смысле оператор с точностью .

Пусть оператор приближает в расширенном смысле оператор с точностью . Докажите, что существует оператор , точно представляющий в расширенном смысле, т.е. выполняется равенство

и такой, что .

Пусть унитарный оператор удовлетворяет условию . Постройте реализующую схему размера в базисе , использующую оператор один раз.

Пусть - некоммутирующие элементы группы - повороты на углы, несоизмеримые с . Докажите, что группа, порожденная и , образует всюду плотное подмножество в .

Пусть - унитарное пространство размерности . Рассмотрим подгруппу - стабилизатор одномерного подпространства, порожденного некоторым единичным вектором . Пусть - произвольный унитарный оператор, не сохраняющий подпространство . Докажите, что множество операторов порождает всю группу .

(Заметим, что в условии этой задачи и можно профакторизовать по подгруппе фазовых сдвигов ).

Докажите, что операторы из стандартного базиса порождают всюду плотное множество в .

Докажите, что фазовые сдвиги можно реализовать в стандартном базисе, используя напрокат дополнительные q-биты.

Докажите, что отрицание и элемент Дойча , где , - иррациональное, образуют полный базис для квантового вычисления.

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

Эта задача довольно сложна, к ее решению лучше приступать после знакомства с разделами 11 и 12 и решения задачи 12.3 (квантовое преобразование Фурье). Предлагаемый путь решения является достаточно изощренным. В статье [<#"22" src="doc_zip1537.jpg" />.

Список литературы

1.Ахо. А., Хопкрофт,Дж., Ульман,Дж Построение и анализ вычислительных алгоритмов М.: Мир, 1979

.Виноградов.И.М Основы теории чисел Изд.8-е, испр. М.: Наука, 1972

.Гэри.М., Джонсон.Д Вычислительные машины и труднорешаемые задачи М.: Мир, 1982

.Китаев.А.Ю. Квантовые вычисления: алгоритмы и исправление ошибок УМН, номер6, 1997

.Клини.С. Математическая логика М.: Мир, 1973

.Клини.С Введение в метаматематику М.: ИЛ, 1957

.Кнут.Д Искусство программирования на ЭВМ. В 3т М.: Мир, 1977

.Кострикин А.И., Манин Ю.И Линейная алгебра и геометрия М.: Наука, 1986

.Мак-Вильямс Ф.,Дж., Слоэн Н.,Дж. А. Теория кодов, исправляющих ошибки М.: Связь, 1979

.Мальцев А. И Алгоритмы и рекурсивные функции М.: Наука, 1965

.Пападимитриу Х., Стаглиц К Комбинаторная оптимизация. Алгоритмы и сложность М.: Мир, 1985

.Прасолов В.В Задачи и теоремы линейной алгебры М.: Наука. Физматлит, 1996

.Роджерс Х Теория рекурсивных функций и эффективная вычислимость М.: Мир, 1972

.Схрейвер А Теория линейного и целочисленного программирования. В 2т М.: Мир, 1991

.Шафаревич И.Р Основные понятия алгебры // Алгебра-1. Итоги науки и техники М.: ВИНИТИ, 1986

.Шенфилд Дж.Р Математическая логика М.: Наука, 1975

.Шенфилд Дж.Р Степени неразрешимости М.: Наука, 1977

Столичный Бизнес Колледж Факультет: «КОМПЬЮТЕРНЫХ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИИ» Курсовая работа По Опера

Больше работ по теме: