NP-полная задача

Введение

Большинство задач, интересных с практической точки зрения, имеют полиномиальные (работающие за полиномиальное время) алгоритмы решения. То есть время работы алгоритма на входе длины n составляет не более O(n k) для некоторой константы k (не зависящей от длины входа). Разумеется, не каждая задача имеет алгоритм решения, удовлетворяющий этому свойству. Некоторые задачи вообще не могут быть решены никаким алгоритмом. Классический пример такой задачи — «проблема остановки» (выяснить останавливается ли данная программа на данном входе). Кроме того, бывают задачи, для которых существует решающий их алгоритм, но любой такой алгоритм работает «долго» — время его работы не есть O(n k) ни для какого фиксированного числа k .

Если мы хотим провести пусть грубую, но формальную границу между «практическими» алгоритмами и алгоритмами, представляющими лишь теоретический интерес, то класс алгоритмов, работающих за полиномиальное время, является разумным первым приближением. Мы рассмотрим, руководствуясь , класс задач, называемых NP-полными. Для этих задач не найдены полиномиальные алгоритмы, однако и не доказано, что таких алгоритмов не существует. Изучение NP-полных задач связано с так называемым вопросом «P = NP». Этот вопрос был поставлен в 1971 году и является сейчас одной из наиболее сложных проблем теории вычислений.

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

Полиномиальное время

Абстрактные задачи

Как уже упоминалось, понятие полиномиально разрешимой задачи принято считать уточнением идеи «практически разрешимой» задачи. Чем объясняется такое соглашение? Во-первых, используемые на практике полиномиальные алгоритмы обычно действительно работают довольно быстро. Второй аргумент в пользу рассмотрения класса полиномиальных алгоритмов — тот факт, что объем этого класса практически не зависит от выбора конкретной модели вычислений. Например, класс задач, которые могут быть решены за полиномиальное время на последовательной машине с произвольным доступом (RAM), совпадает с классом задач, полиномиально разрешимых на машинах Тьюринга. Класс будет тем же и для модели параллельных вычислений, если, конечно, число процессоров ограничено полиномом от длины входа. В-третьих, класс полиномиально разрешимых задач обладает естественными свойствами замкнутости. Например, композиция двух алгоритмов также работает полиномиальное время. Это объясняется тем, что сумма, произведение и композиция многочленов есть многочлен.

Введем следующую абстрактную модель вычислительной задачи. Будем называть абстрактной задачей — произвольное бинарное отношение Q между элементами двух множеств — множества условий I и множества решений S . Например, в задаче поиска кратчайшего пути между двумя заданными вершинами неориентированного графа G = (V , E) условием (элементом I) является тройка, состоящая из графа и двух вершин, а решением (элементом S) — последовательность вершин, составляющих требуемый путь в графе.

В теории NP-полноты рассматриваются только задачи разрешения — задачи, в которых требуется дать ответ «да» или «нет» на некоторый вопрос. Формально её можно рассматривать как функцию, отображающую множество условий I во множество {0, 1}. Например, с задачей поиска кратчайшего пути в графе связана задача разрешения: «по заданному графу G = (V , E), паре вершин u , v ∈ V и натуральному числу k определить, существует ли в G путь между вершинами u и v , длина которого не превосходит k ».

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

Представление данных

Прежде чем подавать на вход алгоритма исходные данные (то есть элемент множества I), надо договориться о том, как они представляются в «понятном для компьютера виде». Будем считать, что исходные данные закодированы последовательностью битов. Формально говоря, представлением элементов некоторого множества S называется отображение e из S во множество битовых строк. Например, целые числа 0, 1, 2, 3, … обычно представляются битовыми строками 0, 1, 10, 11, 100, …

Фиксировав представление данных, мы превращаем абстрактную задачу в строковую, для которой входными данными является битовая строка, представляющая исходные данные абстрактной задачи. Будем говорить, что алгоритм решает строковую задачу за время O(T (n)), если на входных данных (битовой строке) длины n алгоритм работает время O(T (n)). Строковая задача называется полиномиальной, если существует константа k и алгоритм, решающий эту задачу за время O(n k). Сложностной класс P — множество всех строковых задач разрешения, которые могут быть решены за полиномиальное время, т. е. за время O(n k), где k не зависит от входа.

Желая определить понятие полиномиальной абстрактной задачи, мы сталкиваемся с тем, что возможны различные представления данных. Для каждого представления e множества I входов абстрактной задачи Q мы получаем свою строковую задачу. Однако на практике (если исключить такие «дорогие» способы представления, как система счисления с основанием 1) естественные способы представления оказываются обычно эквивалентными, поскольку они могут быть полиномиально преобразованы друг в друга. Будем говорить, что функция f: {0,1}* → {0,1}* вычислима за полиномиальное время, если существует полиномиальный алгоритм A , который для любого x ∈ {0,1}* выдает результат f (x).

Рассмотрим множество I условий произвольной абстрактной задачи разрешения. Два представления e 1 и e 2 этого множества называются полиномиально связанными, если существуют две вычислимые за полиномиальное время функции f 12 и f 21 , для которых f 12 (e 1 (i)) = e 2 (i) и f 21 (e 2 (i)) = e 1 (i) для всякого i ∈ I . В этом случае не имеет значения, какое из двух полиномиально связанных представлений выбрать.

Формальные языки

Для задач разрешения удобно использовать терминологию теории формальных языков. Алфавитом Σ называется любой конечный набор различных символов. Языком L над алфавитом Σ называется произвольное множество строк символов из алфавита Σ (такие строки называются словами в алфавите Σ). Например, можно рассмотреть Σ = {0, 1} и язык L = {10, 11, 101, 111, 1011, …}, состоящий из двоичных записей простых чисел. Будем обозначать символом ε пустое слово, не содержащее символов, а символом Ø — пустой язык, не содержащий слов.

Имеется несколько стандартных операций над языками. Операции объединения и пересечения языков определяются как обычные операции объединения и пересечения множеств. Конкатенацией, или соединением, двух языков L 1 и L 2 называется язык L = { x 1 x 2 | x 1 ∈ L 1 , x 2 ∈ L 2 } Замыканием языка L называется язык L * = {ε} ∪ L ∪ L 2 ∪ L 3 ∪ …, где L k — язык, полученный k -кратной конкатенацией L с самим собой. Операция замыкания называется также *-операцией Клини.

Теперь можно сказать, что строковая задача разрешения является языком над алфавитом Σ. Например, задаче разрешения о существовании в графе пути длины не превосходящей k , соответствует язык PATH = {< G , u , v , k > | G = (V , E) — неориентированный граф, u , v ∈ V ; k ≥ 0 — целое число, и в графе G существует путь из u в v , длина которого не превосходит k .}

Говорят, что алгоритм A допускает слово x ∈ {0,1}*, если на входе x алгоритм выдает результат 1; если же A выдает 0, говорят, что он отвергает слово x . Заметим, что алгоритм может не останавливаться на входе x , или дать ответ отличный от 0, 1. В этом случае он и не допускает, и не отвергает слово x . Алгоритм А допускает язык L , если алгоритм допускает те и только те слова, которые принадлежат языку L . Алгоритм А, допускающий некоторый язык L , не обязан отвергать всякое слово x ∉ L . Если алгоритм A допускает все слова из L , а все остальные отвергает, то говорят, что A распознает язык L . Язык L допускается за полиномиальное время, если имеется алгоритм A , который допускает данный язык, причем всякое слово x ∈ L допускается алгоритмом за время O(n k), где n — длина слова x , а k — некоторое не зависящее от x число. Язык L распознается за полиномиальное время, если некоторый алгоритм A распознает данный язык, причем время работы алгоритма на каждом слове длины n не больше O(n k).

Рассмотренный ранее язык PATH, допускается за полиномиальное время. Нетрудно построить алгоритм, который методом поиска в ширину за полиномиальное время находит кратчайший путь между вершинами u и v в графе G , а затем сравнивает длину найденного пути с данным в условии числом k . Если длина пути не превосходит k , алгоритм выдает 1 и останавливается. В противном случае алгоритм зацикливается, не выдавая никакого ответа. Ясно, что такой алгоритм допускает, но не распознает язык PATH. Однако легко исправить описанный алгоритм таким образом, чтобы слова, не принадлежащие языку, отвергались. Такой алгоритм допускает и распознает язык PATH. Стоит отметить, что некоторые языки (например, для множества всех программ, заканчивающих свою работу) имеют допускающий алгоритм, но не имеют распознающего.

Определение класса задач P мы уже имеем. Дадим определение класса NP. Неформально сложностной класс можно определить как семейство языков, для которых распознающие алгоритмы имеют заданную меру сложности, например заданное время работы. В теории существует множество сложностных классов. Один из них (P) мы уже рассматривали. Есть также не менее важный класс PSPACE — состоящий из задач, решаемых алгоритмами с использованием памяти полиномиального размера. Или класс EXP, состоящий из задач, которые решаются за время O(2 n k). Переформулируем определение класса P: P = { L ⊂ {0,1}* | существует алгоритм A , распознающий L за полиномиальное время.} На самом деле в данной ситуации нет разницы между языками допускаемыми и распознаваемыми за полиномиальное время, о чем свидетельствует следующая теорема.

Теорема

P = { L | L допускается за полиномиальное время}.

Доказательство. Если язык распознается некоторым алгоритмом, то он и допускается тем же алгоритмом. Остается доказать, что если язык L допускается полиномиальным алгоритмом A , то он и распознается некоторым (возможно, другим) полиномиальным алгоритмом A ′. Пусть алгоритм A допускает язык L за время O(n k). Это значит, что существует константа c , для которой A допускает любое слово длины n из L , сделав не более T = c n k шагов. С другой стороны слова не из L алгоритм не допускает (ни за какое время).

Новый алгоритм A ′ моделирует работу алгоритма A и считает число шагов этого алгоритма, сравнивая его с известной границей T . Если за время T алгоритм A допускает слово x , алгоритм A ′ также допускает это слово и выдает 1. Если же A не допускает x за указанное время, то алгоритм A ′ прекращает моделирование и отвергает слово (выдает 0). Замедление работы за счет моделирования и подсчета шагов не так уж велико и оставляет время работы полиномиальным.

Проверка принадлежности языку и класс NP

Выше мы рассматривали задачу разрешения PATH. Эта задача оказалась полиномиальной (и решается с помощью алгоритма поиска в ширину). Допустим, однако, что мы ничего не знаем про поиск в ширину. Тогда задача PATH будет для нас трудной: видя граф G и вершины u и v и зная число k , мы не будем знать, есть ли искомый путь, пока нам его не покажут. Но если он нам станет известен, то мы можем легко проверить, что этот путь — искомый. Именно такая ситуация имеет место для задач из класс NP.

Гамильтонов цикл

Задача поиска гамильтонова цикла в графе изучается уже более ста лет. Гамильтоновым циклом в неориентированном графе G = (V , E) называется простой цикл, который проходит через все вершины графа. Графы, в которых есть гамильтонов цикл, называют гамильтоновыми. Задача о гамильтоновом цикле состоит в выяснении, имеет ли заданный граф G гамильтонов цикл. Формально говоря, HAM-CYCLE = {< G > | G — гамильтонов граф}. Задача о гамильтоновом цикле является NP-полной, и поэтому можно предполагать, что полиномиального алгоритма для нее вообще не существует. На рисунке ниже приведены примеры двух графов, левый из которых является гамильтоновым, правый же не обладает аналогичным свойством.

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

Определить, является ли граф гамильтоновым, за полиномиальное время, скорее всего, невозможно, однако доказательство существования гамильтонова цикла в графе (состоящее в предъявлении гамильтонова пути) можно проверить за полиномиальное время. Назовем проверяющим алгоритмом алгоритм A с двумя аргументами; первый аргумент — входная строка, а второй — сертификат. A допускает вход x , если существует сертификат y , для которого A (x , y) = 1. Язык, проверяемый алгоритмом A: L = { x ∈ {0, 1}*: ∃ y ∈ {0,1}*, A (x , y) = 1}. Другими словами, алгоритм A проверяет язык L , если для любой строки x ∈ L найдется сертификат y , с помощью которого A может проверить принадлежность x к языку L , а для x ∉ L такого сертификата нет. Например, в задаче HAM-CYCLE сертификатом была последовательность вершин, образующая гамильтонов цикл.

Сложностной класс NP

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

Более формально. Язык L принадлежит классу NP, если существует такой полиномиальный алгоритм А с двумя аргументами и такой многочлен p (x) с целыми коэффициентами, что L = { x ∈ {0, 1}* : ∃ y , для которого | y | ≤ p (| x |) и A (x , y) = 1}. В этом случае говорят, что A проверяет L за полиномиальное время.

Ранее уже была рассмотрена задача из класса NP — это задача HAM-CYCLE. Кроме того, всякая задача из P принадлежит также NP. Действительно, если есть полиномиальный алгоритм, распознающий язык, то легко построить проверяющий алгоритм для того же языка — проверяющий алгоритм может просто игнорировать свой второй аргумент (сертификат). Таким образом, P ⊂ NP. В данное время неизвестно совпадают ли классы P и NP, но большинство специалистов полагает, что нет. Наиболее серьезная причина полагать, что P ≠ NP — существование NP полных задач (они будут рассмотрены далее). Кроме проблемы P = NP, остаются открытыми и многие другие вопросы о классе NP. Так, несмотря на огромные усилия исследователей, не известно, замкнут ли класс NP относительно дополнения. Определив сложностной класс co-NP, как множество языков L , для которых ¬ L ∈ NP, можно переформулировать вопрос о замкнутости класса NP относительно дополнения следующим образом: равны ли классы NP и co-NP? Поскольку класс P замкнут относительно перехода к дополнению, P ⊂ NP ∩ co-NP. В то же время остается неизвестным, верно ли равенство P = NP ∩ co-NP. Приведенная ниже иллюстрация, отображает четыре возможных ситуации.

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

NP-полнота и сводимость

Наиболее убедительным аргументом в пользу того, что классы P и NP различны, является существование так называемых NP-полных задач. Этот класс обладает тем важным свойством, что если какая-нибудь NP-полная задача разрешима за полиномиальное время, то и все задачи из класса NP разрешимы за полиномиальное время, то есть P = NP. В частности, задача HAM-CYCLE является NP-полной. Таким образом, научившись решать ее за полиномиальное время, мы получим полиномиальные алгоритмы для всех задач класса NP. Неформально говоря, NP-полные языки являются самыми «трудными» в классе NP. При этом трудность языков можно сравнивать, сводя один язык к другому. Метод сведения является основным при доказательстве NP-полноты многих задач.

Сводимость

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

Теперь дадим формальное определение. Говорят, что язык L 1 сводится за полиномиальное время к языку L 2 (запись: L 1 ≤ P L 2), если существует такая функция f: {0,1}* → {0, 1}*, вычислимая за полиномиальное время, что для любого x ∈ {0, 1}*: x ∈ L 1 равносильно f (x) ∈ L 2 . Функцию f называют сводящей функцией, а полиномиальный алгоритм F , вычисляющий f , — сводящим алгоритмом. Рисунок, приведенный выше, иллюстрирует данное определение сводимости. Запись L 1 ≤ P L 2 можно интерпретировать так: сложность языка L 1 не более чем полиномиально превосходит сложность языка L 2 .

Лемма

Если язык L 1 ⊂ {0, 1}* сводится за полиномиальное время к языку L 2 ⊂ {0, 1}* и L 2 ⊂ P, то L 1 ⊂ P.

Доказательство. Пусть A 2 — полиномиальный алгоритм, распознающий язык L 2 , а F — полиномиальный алгоритм, сводящий язык L 1 к языку L 2 . Построим алгоритм A 1 , который будет за полиномиальное время разрешать язык L 1 , согласно нижеприведенной иллюстрации, а именно: получив на вход x ∈ {0, 1}*, алгоритм A 1 (с помощью алгоритма F) получает f (x) и с помощью алгоритма A 2 проверяет, принадлежит ли слово f (x) языку L 2 . Результат работы алгоритма A 2 на основе f (x) и выдается алгоритмом A 1 в качестве ответа. Определение полиномиальной сводимости гарантирует, что алгоритм A 1 дает правильный ответ; он полиномиален, поскольку полиномиальны алгоритмы F и A 2 .

NP-полнота

Понятие сводимости позволяет формализовать сравнение языков относительно их трудности. Запись L 1 ≤ P L 2 можно интерпретировать так: сложность языка L 1 не более чем полиномиально превосходит сложность языка L 2 . Наиболее трудны в этом смысле NP-полные задачи. Язык L ⊂ {0, 1}* называется NP-полным, если L ∈ NP и L ′ ≤ P L для любого L ′ ∈ NP. Класс NP-полных языков будем обозначать NPC . Языки, которые обладают вторым свойством, но не обязательно отвечают первому, называют NP-трудными. Сформулируем основное свойство NPC языков в виде следующей несложной теоремы:

Теорема

Если некоторая NP-полная задача разрешима за полиномиальное время, то P = NP. Другими словами, если в классе NP существует задача, не разрешимая за полиномиальное время, то все NP-полные задачи таковы.

Доказательство. Пусть L — NP-полный язык, который одновременно оказался разрешимым за полиномиальное время. Тогда для любого языка L ′ ∈ NP из определения NP-полного языка имеем L ′ ≤ P L . Следовательно, L ′ ∈ P, и теорема доказана.

Таким образом, гипотеза P ≠ NP означает, что NP-полные задачи не могут быть решены за полиномиальное время. Видимо, это действительно так, а потому доказательство NP-полноты некоторой задачи является существенным аргументом в пользу ее практической неразрешимости.

Заключение

Итак, какой же практический смысл имеет изучение теории сложности и классификация задач с точки зрения NP-полноты? Ответ очевиден — зачастую гораздо разумнее и эффективнее найти доказательство того, что рассматриваемая задача принадлежит к классу NP-полных, и в соответствие с этим заняться поиском достаточно точных приближенных алгоритмов, нежели безрезультатно тратить время на отыскание полиномиальных алгоритмов ее решения. Ясно, что именно NP-полные задачи играют здесь центральную роль — дело в том, что полиномиальное время является, хоть и первым, но достаточно хорошим приближением понятия «практической разрешимости задачи».

Как уже было упомянуто ранее, определяющим источником данной статьи является . Однако существует немало других интересных книг по данной тематике, заслуживающих пристального внимания со стороны читателя. Среди них хотелось бы выделить , где можно найти большое разнообразие NP-полных задач из самых различных областей. Читателям, желающим подробнее ознакомиться с теорией сложности, на мой взгляд, будет интересен подробный курс лекций , глубоко освещающий данную тематику.

Литература

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ . — М.: МЦНМО, 2001.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с. англ. — М.: Мир, 1982.
Oded Goldreich. Introduction to Complexity Theory — Weizmann Institute of Science, Israel, 1999.

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

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

Алгоритмика

Алгоритмика - это мир, в котором P = NP. В этом мире Профессору везло бы еще меньше, чем в реальности. Так как Профессору нужно поставить в тупик Гаусса задачей, на которую он (Профессор) затем должен сам показать классу верный ответ, он ограничен в выборе задач теми, которые имеют легко проверяемое решение (то есть задачи из NP). Гаусс может использовать метод проверки, чтобы автоматически решить эту задачу.
Метод автоматического получения алгоритма решения проблем из алгоритма проверки верного решения произведет революцию в информатике того мира. Задачи, которые казались неподдающимися, окажутся тривиальными. Почти все задачи оптимизации будут простыми и автоматическими. Например, в проектировании СБИС больше не будут использоваться эвристики, вместо этого будет генерироваться оптимальная проводка, если задан критерий оптимальности. Языки программирования больше не будут содержать инструкции, описывающие как выполнять вычисления. Вместо этого они только будут описывать свойства, которыми должны обладать выходные данные по отношению к входным данным. Компилятор будет самостоятельно переводить язык спецификаций в алгоритм решения.
Менее очевидно, что P=NP сделает тривиальными многие аспекты программ искусственного интеллекта. Можно будет использовать обучающиеся системы, основывающиеся на принципе «бритвы Оккама», чтобы автоматически обучать компьютер выполнять действия, которые могут делать люди. Достаточно будет обеспечить обучающую выборку входных данных и выходных данных, произведенных человеком-экспертом, и компьютер выведет простейший алгоритм, которые будет выдавать те же ответы, что и эксперт. Так, компьютер можно будет научить распознавать и разбирать предложения на естественном языке, нужно только обеспечить достаточное количество примеров верных и неверных предложений (здесь предполагается, что существует некий простой алгоритм, который люди используют для разбора естественных языков).
С другой стороны, в Алгоритмике не будет возможности различить людей и компьютеры с информационной точки зрения. Упомянутые обучающиеся алгоритмы смогут легко научиться имитировать поведение других машин и даже людей. Любой код, который может быть разработан, так же легко может быть взломан. Мало пользы будет от попыток скрыть алгоритм, на котором основан код, так как такой же алгоритм можно будет легко получить, имея небольшое количество пар шифротекст - плейнтекст. Не будет возможности обеспечить доступ к информации нескольких людям, не делая ее таким образом доступной для всех. Поэтому любые способы идентификации должны будут быть основаны на физических измерениях. И безопасность идентификации будет базироваться на неизменности физических параметров и устойчивости к внешним воздействиям каналов передачи данных от измерителя к идентификационному устройству.

Эвристика

Эвристика - это мир, в котором задачи из NP не имеют эффективных решений в худшем случае, но легко решаемы в среднем (для некоторого распределения вероятностей на множестве входов).
Эвристика, в некотором роде, парадоксальный мир. Здесь существуют сложные экземпляры задач из NP, но найти такой сложный экземпляр - сама по себе сложно решаемая задача. В этом мире Профессор будет иметь возможность найти задачи, которые окажутся не по зубам Гауссу. Но ему придется потратить неделю на поиск задачи, которую Гаусс не сможет решить в течение дня, и год, чтобы найти задачу, на которую Гаусс потратит месяц (в данном случае предполагается, что Гаусс имеет некоторое полиномиальное преимущество над профессором, ведь Гаусс, в конце концов, гений). Скорее всего, жизнь не настолько сурова, чтобы предоставлять нам сложные задачи, лишь бы жизнь малиной не казалась. Поэтому для практических целей этот мир почти неотличим от Алгоритмики.
Или все же отличим? В Эвристике среднее время решения задачи из NP зависит от среднего времени «обдумывания» этой задачи. Это несколько усложняет ситуацию. Допустим, в среднем, вычисление решения задачи в два раза дольше придумывания решения. Если мы тратим время T на обдумывание задачи №1, то мы потратим 2T единиц времени на вычисление решения. Решение этой задачи влияет на решение задачи №2, т.е. на обдумывание решения задачи №2 мы потратили 3Т единиц времени. Поэтому на решение задачи №2 будет потрачено 6Т единиц времени. Что приводит к задаче №3, на обдумывание которой мы уже потратили 10Т единиц времени, следовательно 20Т будет потрачено на решение. Так как эта рекурсия экспоненциально растет, уже через несколько шагов мы пересечем границу между «осуществимым» и «нереальным».
В случае дизайна СБИС здесь уже не обязательно будут эффективные решения, так как в данном случае нас мало интересует большинство возможных подходящих под спецификации схем, а важны минимальные варианты, удовлетворяющие спецификациям. Такие схемы могут не иметь хорошего распределения, и, так как, скорее всего, понадобится экспоненциальное время для их поиска, нет никаких гарантий, что они не являются теми самыми «худшими случаями», на которых плохо работают алгоритмы в Эвристике.
В криптографии и сетевой безопасности не будет принципиальных различий с Алгоритмикой. Мало толку будет, если добросовестные пользователи будут тратить много времени на поиск экземпляра задачи, которая могла бы однозначно их идентифицировать, когда злоумышленник может решить этот экземпляр за сравнимое количество времени (предполагается, что злоумышленник, который хочет взломать систему, использует значительно больше ресурсов, чем добросовестный пользователь).

Пессиландия

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

Миникрипт

В Миникрипте есть односторонние функции, но невозможна криптография с открытым ключом. Здесь мы понимаем под криптографией с открытым ключом задачу засекреченного общения через публичные каналы связи, хотя, строго говоря, криптография с открытым ключом - лишь один из способов решения этой задачи.
Односторонние функции могут использоваться для генерации сложных, но решенных задач, а именно: генератор будет выбирать х, вычислять y = F(x) и ставить задачу поиска «найти такой x", что F(x") = y». Таким образом, в Миникрипте Профессор, наконец, сможет одержать верх над Гауссом перед всем классом.
В сети участники смогут идентифицировать себя перед другими пользователями, а также удостоверять сообщения с использованием цифровой электронной подписи. Будет возможно доказывать факты о секрете, не открывая другую секретную информацию, содержащуюся в нем. Если небольшое количество информации заранее передано между участниками, то можно установить надежный секретный код между двумя участниками сети, который позволит им общаться в закрытом порядке, используя открытые каналы связи. Однако, невозможно будет провести тайное голосование через открытые каналы, или обеспечить безопасные переговоры, не пересылая заранее некоторую информацию через защищенные каналы. Не будет возможности создать анонимные цифровые деньги.

Криптомания

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

NP-полные задачи

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

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

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

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

Гамильтоновым путем в графе называется путь, проходящий через каждую вершину в точности один раз. Если при этом путь возвращается в исходную вершину, то он называется гамильтоновым циклом. Граф, в котором есть гамильтонов путь или цикл, не обязательно является полным. Задача о поиске гамильтонова цикла следующим образом сводится к задаче о коммивояжере. Каждая вершина графа - это город. Стоимость пути вдоль каждого ребра графа положим равной 1. Стоимость пути между двумя городами, не соединенными ребром, положим равной 2. А теперь решим соответствующую задачу о коммивояжере. Если в графе есть гамильтонов цикл, то алгоритм решения задачи о коммивояжере найдет циклический путь, состоящий из ребер веса 1. Если же гамильтонова цикла нет, то в найденном пути будет по крайней мере одно ребро веса 2. Если в графе N вершин, то в нем есть гамильтонов цикл, если длина найденного пути равна N, и такого цикла нет, если длина найденного пути больше N.

В 1971 году Кук доказал NP-полноту обсуждаемой в следующем параграфе задачи о конъюнктивной нормальной форме. NP-полнота большого числа задач была доказана путем редукции к ним задачи о конъюнктивной нормальной форме. В книге Гэри и Джонсона, опубликованной в 1979 году, приведены сотни задач, NP-полнота которых доказана.

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

Типичные NP задачи

Каждая из задач, которые мы будем обсуждать, является либо оптимизационной, либо задачей о принятии решения. Целью оптимизационной задачи обычно является конкретный результат, представляющий собой минимальное или максимальное значение. В задаче о принятии решения обычно задается некоторое пограничное значение, и нас интересует, существует ли решение, большее (и задачах максимизации) или меньшее (в задачах минимизации) указанной границы. Ответом в задачах оптимизации служит полученный конкретный результат, а в задачах о принятии решений - «да» или «нет».

Ранее мы занимались оптимизационным вариантом задачи о коммивояжере. Это задача минимизации, и нас интересовал путь минимальной стоимости. В варианте принятия решения мы могли бы спросить, существует ли путь коммивояжера со стоимостью, меньшей заданной константы С. Ясно, что ответ в задаче о принятии решения зависит от выбранной границы. Если эта граница очень велика (например, она превышает суммарную стоимость всех дорог), то ответ «да» получить несложно. Если эта граница чересчур мала (например, она меньше стоимости дороги между любыми двумя городами), то ответ «нет» также дается легко. В остальных промежуточных случаях время поиска ответа очень велико и сравнимо со временем решения оптимизационной задачи. Поэтому мы будем говорить вперемешку о задачах оптимизации и принятия решений, используя ту из них, которая точнее отвечает нашим текущим целям.

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

Раскраска графа

Как мы уже говорили, граф G= (V, Е) представляет собой набор вершин, или узлов, V и набор ребер Е соединяющих вершины попарно. Здесь мы будем заниматься только неориентированными графами. Вершины графа можно раскрасить в разные цвета, которые обычно обозначаются целыми числами. Нас интересуют такие раскраски, в которых концы каждого ребра окрашены разными цветами. Очевидно, что в графе с N вершинами можно покрасить вершины в N различных цветов, но можно ли обойтись меньшим количеством цветов? В задаче оптимизации нас интересует минимальное число цветов, необходимых для раскраски вершин графа. В задаче принятия решения нас интересует, можно ли раскрасить вершины в С или менее цветов.

У задачи о раскраске графа есть практические приложения. Если каждая вершина графа обозначает читаемый в колледже курс, и вершины соединяются ребром, если есть студент, слушающий оба курса, то получается весьма сложный граф. Если предположить, что каждый студент слушает 5 курсов, то на студента приходится 10 ребер. Предположим, что на 3500 студентов приходится 500 курсов. Тогда у получившегося графа будет 500 вершин и 35 000 ребер. Если на экзамены отведено 20 дней, то это означает, что вершины графа нужно раскрасить в 20 цветов, чтобы ни у одного студента не приходилось по два экзамена в день.

Разработка бесконфликтного расписания экзаменов эквивалентна раскраске графов. Однако задача раскраски графов принадлежит к классу NP, поэтому разработка бесконфликтного расписания за разумное время невозможна. Кроме того при планировании экзаменов обычно требуется, чтобы у студента было не больше двух экзаменов в день, а экзамены по различным частям курсам назначаются в один день. Очевидно, что разработка «совершенного» плана экзаменов невозможна, и поэтому необходима другая техника для получения по крайней мере неплохих планов.

Раскладка по ящикам

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

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

Упаковка рюкзака

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

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

Задача о суммах элементов подмножеств

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

Задача об истинности КНФ-выражения

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

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

Задача планирования работ

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

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

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

NP класс

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

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

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

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

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

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

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

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

Рассмотрим следующий алгоритм.

В этом алгоритме рассмотрение каждого варианта, т.е. последовательности соединённых дугами вершин требует n шагов. Следовательно, каждая процедура ВЫБОР (иначе каждая копия алгоритма просмотра одного пути) работает не более, чем полиномиальное время, точнее имеет сложность порядка . Таким образом, задача выяснения существования в ориентированном графе гамильтонового цикла, длина которого меньше или равна M, является NP задачей.

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

Вопрос о том, будет ли P=NP является открытой проблемой теории сложности. Широко распространено мнение, что , следовательно, .

Примеры задач из класса NP:

1) выяснение выполнимости формулы логики высказываний, записанной в к.н.ф.;

2) нахождение целочисленных решений системы линейных уравнений;

3) задача распознавания простого числа;

4) выяснение гамильтоновости графа;

5) задача коммивояжёра ;

8) составление расписаний, учитывающих определённые условия;

10) динамическое распределение памяти. Раскроем эту проблему. Пусть заданы А – множество элементов данных, размер , каждого элемента данных , время поступления , и время окончания работы с элементом данных , положительное целое число D – размер области памяти. Вопрос. Существует ли для множества элементов данных допустимое распределение памяти? Иначе говоря, существует ли такая функция σ: А→{1,2,3,…}, что для каждого элемента интервал

содержится в , причём для любых , если , то либо , либо .

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

Рассмотрим сводимость задач. Говорят, что задача Z 1 сводится к задаче Z 2 , если метод решения задачи Z 2 можно преобразовать в метод решения задачи Z 1 . Сводимость называется полиномиальной если указанное преобразование можно осуществить за полиномиальное время.

Если одновременно задача Z 1 полиномиально сводится к задаче Z 2 и Z 2 полиномиально сводится к задаче Z 1 , то задачи Z 1 и Z 2 полиномиально эквивалентны.

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

NP-трудная задача имеет тот смысл, что эта задача не проще , чем «самая трудная в NP».

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

Класс NP- полных задач обладает следующими свойствами .

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

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

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

Первой задачей, для которой было доказано, что она является NP-полной, была проблема о выполнимости (см. задачу 1 в § 4), именно, имеет место следующая теорема.

Теорема 7.1 (теорема Кука). Задача выяснения выполнимости формулы логики высказываний, представленной в к.н.ф., является NP-полной.

Все приведённые ранее примеры NP-задач (задачи 1-12) являются NP-полными задачами. Список NP-полных задач в настоящее время содержит несколько сотен задач и продолжает пополняться. Многие вновь установленные NP-полные задачи печатаются в журнале Journal of Algorithms. В действительности о большей части задач комбинаторной оптимизации известна либо полиномиальная разрешимость, либо NP-полнота, что является ещё одним подтверждением гипотезы P≠NP.

Класс Е.

Считается, что алгоритм имеет полиномиальную временную сложность, если существует полином p(x) такой, что на любом входном слове длины n алгоритм завершает вычисления после выполнения не более чем p(n) операций. Если такого полинома не существует, временная сложность считается экспоненциальной. Таким образом для них число операций возрастает быстрее значений любого полинома.

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

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

Большинство экспоненциальных алгоритмов – это просто варианты полного перебора. Экспоненциальные алгоритмы не считаются «хорошими», в отличие от полиномиальных алгоритмов, которые, как уже указывалось, считаются «хорошими». К экспоненциальным задачам относятся задачи, в которых требуется построить множество всех подмножеств данного множества, все полные подграфы некоторого графа или же все поддеревья некоторого графа.

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

Для решения задачи линейного программирования существует так называемый симплекс-метод (алгоритм), который хотя и экспоненциален в худшем случае – уверено работает на практике для задач достаточно большого размера. Отметим, что для решения задачи линейного программирования Хачиян Л. Г. в 1979 г. предложил алгоритм эллипсоидов, который имеет полиномиальную временную сложность.

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

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

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

Экспоненциальная сложность задачи имеет следующие аспекты:

-для отыскания решения требуется экспоненциальное время;

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

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

Ёмкостная (ленточная) сложность алгоритма

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

Пусть машина Тьюринга вычисляет значение функции f.

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

Определим Sf(x) как длину активной зоны при работе машины Т на числе х, если f(x) определено. В противном случае значение Sf(x) будем считать неопределённым. Функцию Sf(x) назовём ленточной сложностью.

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

Для задач вводятся понятия задач с полиномиальной потребной памятью, с NP-потребной памятью и т.д.

Имеет место следующая теорема:

Теорема . Для ленточной (ёмкостной) характеристики сложности вычисления функции f имеет место оценка

где -временная сложность вычисления f(x).

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

Эта теорема показывает, что если известна временная сложность, то можно оценить сверху ленточную сложность.

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

словами, существует ли такое назначение регистров f: V → {1,2,3,…,K} , что еслиf(u)=f(v) для некоторыхu,v V, то из неравенстваs(u) ≤ s(v) следует, чтоs(u)+l(u) ≤ s(v) иs(v)+l(v)(mod N) ≤ s(u)?

Если число K заранее фиксировано, то задача разрешима за полиномиальное время .

§ 5. NP -полные и NP -трудные задачи

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

Говорят, что задача Z 1 сводится к задачеZ 2 если метод решения задачиZ 2 можно преобразовать в метод решения задачиZ 1 . Сводимость называется полиномиальной если указанное преобразование можно осуществить за полиномиальное время.

Если одновременно задача Z 1 полиномиально сводится к задачеZ 2 иZ 2 полиномиально сводится к задачеZ 1 , то задачиZ 1 иZ 2 полиномиально эквивалентны.

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

NP- трудная задача имеет тот смысл, что эта задача не проще, чем «самая трудная вNP ».

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

Класс NP- полных задач обладает следующими свойствами.

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

2. Если бы удалось построить полиномиальный алгоритм для какой-нибудь NP -полной задачи, то это бы означало

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

Первой задачей, для которой было доказано, что она является NP - полной, была проблема о выполнимости (см. задачу 1 в § 4), именно, имеет место следующая теорема.

Все приведённые ранее примеры NP- задач (задачи 1-12) являютсяNP - полными задачами. Список NP -полных задач в настоящее время содержит несколько сотен задач и продолжает пополняться. Многие вновь установленные NP -полные задачи печатаются в журнале Journal of Algorithms. В действительности о большей части задач комбинаторной оптимизации известна либо полиномиальная разрешимость, либоNP - полнота, что является ещё одним подтверждением гипотезыP ≠ NP .

§ 6. Класс Е

Как уже указано, считается, что алгоритм имеет полиномиальную временную сложность, если существует полином p(x) такой, что на любом входном слове длиныn алгоритм завершает вычисления после выполнения не более чемp(n) операций. Если такого полинома не существует,временная сложность считается экспоненциальной . Таким образом для них число операций возрастает быстрее значений любого полинома.

Кроме этого определения существует и второе определение: алгоритм имеет экспоненциальную временную сложность если его временная сложность имеет порядок не меньше, чем сa n , гдес >0, a (a > 1) - постоянные. Иначе, временная сложностьf(n) является экспоненциальной, если существуют постоянныес >0, a >1 , что

саn ≤ f(n)

для всех, кроме конечного числа значений n .

При первом определении, например задача, имеющая сложность порядка 0(n log 2 n ) (0(n log 2 n ) =0(2 (log 2 n) 2 ) ) будет отнесена к задаче с экспоненциальной временной сложностью, а по второму определению – нет.

Отметим, что функция n log 2 n хотя и растет быстрее любого полинома, но растёт медленнее, чем, например2 n .

Большинство экспоненциальных алгоритмов – это просто варианты полного перебора. Экспоненциальные алгоритмы не считаются «хорошими», в отличие от полиномиальных алгоритмов, которые, как уже указывалось, считаются «хорошими». К экспоненциальным задачам относятся задачи, в которых требуется построить множество всех подмножеств данного

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

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

Примеров экспоненциальных алгоритмов успешно используемых на практике мало. Более того даже для полиномиальных алгоритмов представляют практический интерес алгоритмы сложность которых имеет порядок n 2 илиn 3 . Ясно, что алгоритмы со сложностью порядкаn 100 вряд ли будут практически используемы.

Экспоненциальная сложность задачи имеет следующие аспекты: -для отыскания решения требуется экспоненциальное время;

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

§ 7. Ёмкостная (ленточная) сложность алгоритма

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

Пусть машина Тьюринга вычисляет значение функции f.

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

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

Определим S f (x) как длину активной зоны при работе машиныТ на числех , еслиf(x) определено. В противном случае значениеS f (x) будем считать неопределённым. ФункциюS f (x) назовёмленточной сложностью .

Для задач вводятся понятия задач с полиномиальной потребной памятью, с NP -потребной памятью и т.д.

Имеет место следующая теорема:

Теорема 7.2. Для ленточной (ёмкостной) характеристики сложности вычисления функцииf имеет место оценка

Sf (x)≤ x+1+ tf (x),

где t f (x) -временная сложность вычисленияf(x) .

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

Эта теорема показывает, что если известна временная сложность, то можно оценить сверху ленточную сложность.

§ 8. Вопросы и темы для самопроверки

1. Понятие о сложности вычислений.

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

3. Временная сложность алгоритма. Временная сложность задачи.

4. Временная сложность алгоритма в наихудшем случае, временная сложность алгоритма в среднем.

5. Может ли, что для решения одной и той же задачи существовать алгоритмы разной сложности? Если да, то какова сложность задачи?

6. Полиномиальная сложность алгоритма, задачи.

7. Классификация задач по сложности.

8. Класс Р , примеры задач из этого класса.

9. NP класс.

10. Недетерминированная машина Тьюринга, её отличие от детерминированной машины Тьюринга.