Подзоров С.Ю. Теория алгоритмов. Полный конспект лекций по курсу

Подождите немного. Документ загружается.

3. Устройство — это машина Шенфилда, ϕ

(x) — функция, вычис-

ляемая программой для машины Шенфилда с номером

e. Пусть

(x) = M

(x) — максимальное число, которое будет содержаться

в регистрах машины в ходе вычислений по программе с номером

e. Можно опять доказать, что семейство {M

(x)}

e∈N

удовлетворяет

определению 29.

Можно привести множество других примеров.

Утверждения, которые можно доказать для произвольной меры вы-

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

примеров. Такие утверждения принято называть машинно-независимы-

ми. Приведем несколько примеров машинно-независимых результатов.

Теорема 14 (о неограниченности сложности) Пусть {Φ

(x)}

e∈N

—

мера вычислительной сложности и b(x) — рекурсивная функция. Суще-

ствует рекурсивная функция f(x), такая что для любого e ∈ N если

f = ϕ

, то Φ

(x) > b(x) почти для всех

Доказательство. Без доказательства ¤

Теорема 14 показывает, что сложность вычислений невозможно огра-

ничить сверху никакой рекурсивной функцией. Какой бы машинный ре-

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

функции b(x) всегда найдется другая рекурсивная функция f (x), такая

что любая программа, вычисляющая функцию f, должна почти для всех

x затратить больше ресурсов, чем значение b на аргументе x. Для срав-

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

части курса: если в качестве меры вычислительной сложности рассмат-

ривать время вычисления на машине Тьюринга (семейство {t

(x)}

e∈N

из

первого примера), то для любой примитивно рекурсивной функции f су-

ществует программа P

, такая что f = ϕ

и t

(x) 6 C(x) почти для всех x

(это легко следует из следствия 6 и определения функции C(x)). Таким

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

можно ограничить рекурсивной функцией C. Для каждой рекурсивной

функции это сделать уже невозможно.

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

машин Шенфилда.

То есть для всех, за исключением конечного числа. Смотри примечание на стра-

нице 45

121

В формулировке теоремы 14 Φ

(x) > b(x) почти для всех x. Это огра-

ничение существенно; усилить теорему 14, доказав, что Φ

(x) > b(x) для

всех без исключения x не удастся. В принципе, понятно, почему это так,

если мы рассмотрим какой-нибудь конкретный пример меры сложности;

например, время вычисления. Пусть дана программа P , вычисляющая

функцию f(x). Для любого конечного множества аргументов {x

, . . . , x

}

можно так видоизменить программу P , что модифицированная програм-

ма P

будет вычислять f(x) значительно быстрее, если x принадлежит

нашему конечному множеству (и чуть-чуть медленнее, если x ему не при-

надлежит). Работа программы P

должна начинаться с проверки усло-

вия: верно ли, что аргумент x принадлежит {x

, . . . , x

}? Если ответ по-

ложительный, то программа P

дает результат немедленно, а если нет,

то запускает программу P . Поскольку значения любой функции на за-

ранее заданном конечном числе аргументов можно задать явно, в виде

таблицы, то сложность вычислений имеет смысл рассматривать только

с точностью до конечного числа аргументов, то есть в ”асимптотике”.

Теорема 14, в принципе, довольно проста (ее доказательство можно

даже рекомендовать слушателям курса в качестве упражнения). Приве-

дем формулировку другой, более сложной (но и более интересной) тео-

ремы.

Теорема 15 (об ускорении) Пусть {Φ

(x)}

e∈N

— мера вычислитель-

ной сложности и r(x) — произвольная рекурсивная функция. Существует

рекурсивная функция f, такая что для каждого i ∈ N если f = ϕ

, то

существует j ∈ N, для которого f = ϕ

и r(Φ

(x)) < Φ

(x) почти для всех

значений x.

Доказательство. Без доказательства ¤

Из теоремы об ускорении, в частности, следует, что для некоторых

рекурсивных функций не существует оптимальной программы вычис-

ления. Пусть, например, мера сложности — это время вычисления, а

r(x) = 100x. Применим теорему 15 к этой функции r и получим некото-

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

f, найдется другая программа, которая вычисляет ту же самую функ-

цию f, причем почти для всех аргументов вторая программа делает это в

100 раз быстрее, чем первая. Если мы, например, улучшим конструкцию

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

ем так, что новая машина будет выполнять в 100 раз больше операций

122

в секунду, чем старая, то все равно вторая программа на старой машине

будет работать быстрее, чем первая на новой (почти для всех входных

данных).

Закончим этот раздел еще одной достаточно курьезной теоремой.

Теорема 16 (о пробелах) Пусть {Φ

(x)}

e∈N

— мера вычислительной

сложности и r(x) — рекурсивная функция, для которой r(x) > x при

всех x. Тогда существует рекурсивная функция b(x), такая что если для

некоторого e Φ

(x) > b(x) почти для всех x, то Φ

(x) > r(b(x)) почти для

всех x

Доказательство. Без доказательства ¤

Значение теоремы о пробелах лучше всего понять, если рассматри-

вать ее вместе с теоремой 14. Пусть, для примера, опять Φ

(x) = t

(x) —

время вычисления значения ϕ

(x) по программе P

. Рассмотрим функ-

цию r(x) = 100x и применим к ней теорему о пробелах. Получим рекур-

сивную функцию b(x). По теореме 14 существуют рекурсивная функция

f, такая что время вычисления f(x) по любой программе больше, чем

b(x) почти для всех x. А по теореме о пробелах это время должно быть

даже больше, чем 100b(x). Таким образом, в упорядочивании функций

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

вычисления которых меньше, чем b(x) и функции, время вычисления ко-

торых больше, чем 100b(x), но нет функций, время вычисления которых

лежало бы в интервале [b(x), 100b(x)]. Вместо r (x ) = 100x можно было

взять и r(x) = 1000000x, и r(x) = x

1000000

, и даже r(x) = C(x); чем быст-

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

4.3 P = NP?

В отличие от предыдущего раздела здесь мы конкретизируем ресурс —

время (количество шагов) вычисления и устройство — машину Тьюрин-

га. Однако наши рассмотрения носят значительно более широкий харак-

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

Здесь допускается, что функция ϕ

может быть не всюду определенной. Для этого

следует положить Φ

(x) = ∞ в тех случаях, когда ϕ

(x) не определено.

123

но и для любой машины, которая ”полиномиально” сводится к ней

. В

частности, все известные детерминированные (см. ниже) модификации

машины Тьюринга (машина Тьюринга с лентой, бесконечной в оба кон-

ца, с несколькими лентами, с квадратной ”лентой”, с прямым доступом к

памяти) сводятся к известной нам машине с одной лентой, бесконечной

с одного конца, ”полиномиально”.

Пусть Σ — конечный алфавит, не содержащий символы n и m. Под

программой мы будем понимать программу для машины Тьюринга, пред-

назначенную для работы со словами этого алфавита. Каждая частичная

функция из Σ

∗

в Σ

∗

, вычислимая хоть по какому-нибудь алгоритму, со-

гласно тезису Тьюринга вычислима при помощи некоторой программы

(см. определение 13). Для программы P , вычисляющей функцию из Σ

∗

, через t

(w) обозначим количество шагов, которое машина, работаю-

щая по программе P , сделает при вычислении значения этой функции на

аргументе w ∈ Σ

∗

. Скажем, что функция f : Σ

∗

→ Σ

∗

вычислима за поли-

номиальное время (или что она принадлежит классу P), если существует

программа P , вычисляющая эту функцию, такая что t

(w) 6 p(|w|) для

всех w ∈ Σ

∗

, где p — некоторый полином

. Будем говорить, что функция

f : Σ

∗

→ Σ

∗

вычислима за экспоненциальное время (или что она принад-

лежит классу EXP), если существует программа P , вычисляющая эту

функцию, такая что t

(w) 6 2

p(|w|)

для всех w ∈ Σ

∗

, где p — некоторый

полином.

Классы P и EXP определены для ”символьных” функций, то есть для

функций из Σ

∗

в Σ

∗

. Это принципиальный момент, поскольку нам важна

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

мы привыкли иметь дело с ”числовыми” функциями, и здесь возника-

ет одна сложность: как измерять длину входных данных? Существует

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

тельности символов и, к сожалению, некоторые из них не сводятся друг

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

классы P и EXP для числовых функций, нам надо зафиксировать спо-

соб записи чисел. В теории сложности принято следующее определение:

Скажем, что некая машина сводится к машине Тьюринга ”полиномиально”, если

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

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

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

ющей программе не превосходит p(t).

Напомним, что через |w| обозначается длина слова w.

124

функция f : N → N принадлежит классу P (или EXP), если функция из

g : {0, 1}

∗

→ {0, 1}

∗

, такая что для любого n ∈ N g от двоичной

записи

числа n равно двоичной записи числа f(n), принадлежит классу P (или

EXP).

Классы P и EXP очень важны в практическом плане. Большинство

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

решения прикладных задач, принадлежат классу EXP

и могут быть

посчитаны лишь при малых значениях аргументов: все же экспонента

растет слишком быстро. С полиномами дела обстоят лучше, посколь-

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

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

алгоритм решения которых уже известен. Имеется достаточно много ос-

нований для того, чтобы рассматривать в качестве ”практически вычис-

лимых функций” функции, вычислимые за полиномиальное время

Для дальнейших рассмотрений сузим круг задач, ограничившись так

называемыми задачами распознавания. Пусть Σ — конечный алфавит

и L ⊆ Σ

∗

— язык этого алфавита. Без ограничения общности можно

считать, что 0, 1 ∈ Σ. Связанная с языком L задача распознавания —

это задача вычисления характеристической функции χ

, то есть такой

Вместо двоичной можно взять десятичную, шестнадцатиричную и т. п. запись

числа, но не ”одноичную”, которую мы все время рассматривали ранее. Машина Тью-

ринга не может преобразовать двоичную запись числа n в слово 1

за полиномиаль-

ное время. Выбор позиционной системы счисления очень естественен: на практике мы

привыкли работать с десятичной записью чисел, а компьютеры работают с двоичным

представлением данных.

Конечно, есть вычислимые функции, не принадлежащие классу EXP; например,

функция C(x). Однако все они представляют интерес исключительно в рамках аб-

страктной теории. Таковой же является функция, существование которой утвержда-

ется в теореме об ускорении: для нее не существует оптимального алгоритма, но его не

существует за счет того, что любой алгоритм требует очень большого объема вычис-

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

деле. Здесь можно провести параллель с матанализом. Известны примеры различ-

ных ”паталогий” (коврик Серпинского, неизмеримое множество), однако все кривые,

с которыми приходится сталкиваться на практике, все же имеют длину и нулевую

площадь.

Хотя все эти соображения все же достаточно условны. Например, если есть два

алгоритма для вычисления одной и той же функции f, причем первый считает f(x)

за x

100

шагов, а второй — за x

[ln ln x]

шагов, то для тех аргументов, для которых значе-

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

удобнее первого.

125

функции из Σ

∗

в Σ

∗

, что

(w) =

(

1, w ∈ L

0, w 6∈ L.

Скажем, что задача распознавания принадлежности слов языку L реша-

ется за полиномиальное (экспоненциальное) время (или принадлежит

классу P (EXP)), если χ

∈ P (χ

∈ EXP). Далее мы будет говорить

о классах P и EXP, имея в виду совокупность задач распознавания,

принадлежащих этим классам.

На практике задачам распознавания обычно придают более естествен-

ную формулировку. Приведем несколько примеров задач.

1. Эквивалентность детерминированных конечных автоматов. Пусть

даны два конечных автомата одного и того же алфавита Σ: тре-

буется определить, распознают ли они один и тот же язык. Более

формально: необходимо ввести некоторый ”естественный” способ

задания всех пар детерминированных автоматов алфавита Σ при

помощи слов некоторого другого алфавита Σ

. Требуется решить

задачу распознавания языка, состоящего из всех слов алфавита Σ

задающих пары эквивалентных автоматов.

2. Эквивалентность недетерминированных конечных автоматов. То

же самое, но только автоматы могут быть недетерминированны-

ми.

3. Задача коммивояжера. Дан список городов и стоимость проезда из

каждого в каждый. Кроме того, дано число B, которое является

”бюджетом” поездки. Требуется определить, может ли коммивоя-

жер посетить каждый из городов, перечисленных в списке, не вы-

ходя за рамки бюджета

4. Задача проверки истинности формулы. Дана формула исчисления

В более общей постановке задача коммивояжера заключается в нахождении оп-

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

ваемая задача оптимизации. Формулировка с бюджетом поездки превращает задачу

коммивояжера в задачу распознавания.

126

высказываний

: требуется определить, может ли эта формула быть

истинной.

5. Существование эйлерова цикла в графе. Дан направленный конеч-

ный граф (множество вершин и стрелок): требуется определить,

существует ли путь, проходящий через каждую стрелку ровно по

одному разу.

6. Существование гамильтонова цикла в графе. Дан направленный

конечный граф: требуется определить, существует ли путь, прохо-

дящий через каждую вершину ровно по одному разу.

7. Задача о разбиении. Дана последовательность натуральных чисел:

требуется проверить, можно ли разбить эту последовательность на

две части так, чтобы суммы чисел в каждой из частей совпадали.

Каждая из этих задач разрешима за экспоненциальное время, то есть

принадлежит классу EXP. Для первой и пятой задач найдены полиноми-

альные алгоритмы: они принадлежат классу P. Про остальные задачи

это не известно

. Правда, у большинства этих задач есть одна суще-

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

Прежде чем дать формальное определение этого класса, поясним эту

особенность на неформальном уровне.

Рассмотрим, для примера, задачу коммивояжера. Пусть дано n го-

родов. Простейший (так называемый ”полнопереборный”) алгоритм за-

ключается в том, что мы по очереди рассмотриваем все n! возможных

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

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

алгоритма будет сравнимо c n!; этот алгоритм экспоненциален (2

6 n! 6

6 2

почти для всех n). Однако если некто, с помощью необъяснимой

Определение этого понятия можно найти практически в любом учебнике по мате-

матической логике. Отметим еще, что для этой задачи не надо вводить алфавит, слова

которого описывают формулы, поскольку формулы уже являются словами некото-

рого алфавита. Другими словами, эта задача является задачей распознавания уже в

исходной формулировке.

С одной оговоркой. Для задачи о разбиении не известен полиномиальный алго-

ритм для определения того, существует ли разбиение, при условии что числа в ис-

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

Если же задавать числа в ”одноичной” записи, то такой алгоритм есть.

Определение смотри ниже.

127

интуиции, угадает оптимальный маршрут и скажет его, то нам останет-

ся только проверить, укладывается ли он в рамки бюджета. А простая

проверка требует уже значительно меньше времени. В двух словах суть

этой задачи можно сформулировать так: трудно найти ответ, но легко его

проверить. Каждая из перечисленных выше задач, для которой не изве-

стен полиномиальный алгоритм решения, может быть охарактеризована

подобным образом. И если бы мы смогли научить машину Тьюринга уга-

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

шин в гамильтоновом цикле графа, разбиение последовательности чисел

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

появился бы полиномиальный алгоритм решения.

Для формализации ”угадывания” введем так называемую недетерми-

нированную машину Тьюринга. Недетерминированная машина Тьюрин-

га — это та же самая машина (с лентой, головкой и т. д.), в программе

для которой может присутствовать несколько команд вида qa → . . . с

разной правой частью. Если в ходе выполнения программы головка ока-

зывается в состоянии q и указывает на ячейку ленты с записанным в

ней символом a, то может быть выполнена любая из команд, и машина

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

ей известными соображениями

. В процессе вычисления такая маши-

на может сталкиваться с выбором из нескольких возможностей сколько

угодно раз: соответственно, для нее существует множество путей, по ко-

торым она может вести вычисления. Если один из путей заканчивается

переходом в конечное состояние, то можно подсчитать количество ша-

гов, которые машина должна проделать, идя по этому пути, и результат,

который на этом пути получен.

Пусть L ⊆ Σ

∗

— язык конечного алфавита Σ. Скажем, что задача

распознавания принадлежности слов языку L недетерминированно ре-

шается за полиномиальное время (или принадлежит классу NP), если

существует программа P для недетерминированной машины Тьюринга,

работающая с алфавитом Σ, такая что для любого w ∈ Σ

∗

1. все возможные пути вычисления по программе P из состояния, за-

даваемого конфигурацией hw, q

, 1i, завершаются не более чем за

p(|w|) шагов вычисления, где p — некоторый полином;

2. если w ∈ L, то хотя бы один из возможных путей вычисления дает

Это очень похоже на недетерминированный конечный автомат.

128

результат 1; в противном случае все пути вычисления приводят к

результату 0.

Задачи из класса NP постоянно встречаются на практике. В частно-

сти, все перечисленные выше семь задач (кроме, возможно, второй), а

также многие другие принадлежат классу NP.

Теорема 17 Справедливы включения: P ⊆ NP ⊆ EXP и P ⊂ EXP.

Доказательство. Без доказательства ¤

Утверждение теоремы 17 — это практически все, что известно совре-

менной науке о взаимоотношении классов P, NP и EXP. Из-за того, что

включение P ⊂ EXP — строгое, хотя бы одно из включений (а, может

быть, и оба) в ряду P ⊆ NP ⊆ EXP должно быть строгим. Какое из

них какое — неизвестно, несмотря на то, что проблема нахождения поли-

номиальных алгоритмов для задач из класса NP имеет большое прак-

тическое значение и в настоящее время признана одной из центральных

проблем современной математики

Завершая последний раздел курса, покажем, как можно свести про-

блему ”P = NP” к выяснению вопроса о принадлежности классу P од-

ной единственной задачи. Пусть L

, L

— два языка конечного алфави-

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

полиномиально сводится к проблеме распознавания принадлежности

слов языку L

, если существует функция f : Σ

∗

→ Σ

∗

, вычислимая за

полиномиальное время, такая что для любого w ∈ Σ

∗

w ∈ L

↔ f(w) ∈

. Ясно, что в случае наличия полиномиальной сводимости если про-

блема распознавания языка L

решается за полиномиальное время, то

аналогичная проблема для L

также решается за полиномиальное вре-

мя. Для ответа на вопрос ”w ∈ L

?” можно сначала за полиномиальное

время вычислить f(w), а затем, затратив полиномиальное время, отве-

тить на вопрос ”f(w) ∈ L

?”.

Определение 30 Задача распознавания называется NP-полной, если

любая другая задача распознавания, принадлежащая классу NP, поли-

номиально сводится к ней.

За решение этого вопроса обещаны большие денежные премии. В частности, за

решение проблемы ”P = NP?” один из американских институтов предлагает 1000000

долларов (см. http://www.claymath.org/Millennium_Prize_Problems).

Это напоминает определение m-сводимости.

129

Таким образом, если дана какая-нибудь NP-полная задача, то ре-

шить проблему ”P = NP” можно, если установить (или опровергнуть)

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

В приведенном выше списке задачи под номерами 3, 4, 6 и 7 являются

NP-полными. Мы оставляем этот факт без доказательства.

130