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

NP ­ полные задачи. Примеры         алгоритмов NP­полная задача — задача из класса В теории     NP, к которой можно свести л юбую другуюзадачу из класса NP за полиномиальное время. Таким образом, NP­полные зад ачи образуют в некоторомсмысле подмножество «самых сложных» задач в классе NP; и есл и для какой­то из них будет найден«быстрый» алгоритм решения, то и любая другая задача  из класса NP может быть решена так же «быстро». Введение Большинство задач, интересных с практической точки зрения, имеют полиномиальные  (работающие за полиномиальное время) алгоритмы решения. То есть время работы  алгоритма на входе длины n составляет не более O(nk) для некоторой константы k (не  зависящей от длины входа). Разумеется, не каждая задача имеет алгоритм решения,  удовлетворяющий этому свойству. Некоторые задачи вообще не могут быть решены  никаким алгоритмом. Классический пример такой задачи — «проблема остановки»  (выяснить останавливается ли данная программа на данном входе). Кроме того, бывают  задачи, для которых существует решающий их алгоритм, но любой такой алгоритм  работает «долго» — время его работы не есть O(nk) ни для какого фиксированного числа k. Если мы хотим провести пусть грубую, но формальную границу между «практическими»  алгоритмами и алгоритмами, представляющими лишь теоретический интерес, то класс  алгоритмов, работающих за полиномиальное время, является разумным первым  приближением. Мы рассмотрим, руководствуясь [1], класс задач, называемых 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(nk). Сложностной класс P — множество всех  строковых задач разрешения, которые могут быть решены за полиномиальное время, т. е. за время O(nk), где k не зависит от входа. Желая определить понятие полиномиальной абстрактной задачи, мы сталкиваемся с тем,  что возможны различные представления данных. Для каждого  представления e множества Iвходов абстрактной задачи Q мы получаем свою строковую  задачу. Однако на практике (если исключить такие «дорогие» способы представления, как  система счисления с основанием 1) естественные способы представления оказываются  обычно эквивалентными, поскольку они могут быть полиномиально преобразованы друг в  друга. Будем говорить, что функцияf: {0,1}* → {0,1}* вычислима за полиномиальное  время, если существует полиномиальный алгоритм A, который для любого x ∈ {0,1}*  выдает результат f(x). Рассмотрим множество I условий произвольной абстрактной задачи разрешения. Два  представления e1 и e2 этого множества называются полиномиально связанными, если  существуют две вычислимые за полиномиальное время функции f12 и f21, для  которых f12(e1(i)) = e2(i) и f21(e2(i)) = e1(i) для всякого i ∈ I. В этом случае не имеет значения, какое из двух полиномиально связанных представлений выбрать. Формальные языки Σ  называется любой конечный набор различных  Для задач разрешения удобно использовать терминологию теории формальных  языков. Алфавитом  символов. Языком L над алфавитом  символов из алфавита  можно рассмотреть Σ = {0, 1} и языкL = {10, 11, 101, 111, 1011, …}, состоящий из  двоичных записей простых чисел. Будем обозначать символом ε пустое слово, не  содержащее символов, а символом Ø — пустой язык, не содержащий слов. Σ  называется произвольное множество строк  Σ  (такие строки называются  словами в алфавите  Σ ). Например, Имеется несколько стандартных операций над языками.  Операции объединения и пересечения языков определяются как обычные операции  объединения и пересечения множеств.Конкатенацией, или соединением, двух  языков L1 и L2 называется язык L = {x1x2 | x1 ∈ L1, x2 ∈ L2} Замыканием языка L называется язык L* = { }ε  ∪ L ∪ L2 ∪ L3 ∪ …, где Lk — язык, полученный k­кратной конкатенацией L с  самим собой. Операция замыкания называется также *­операцией Клини.  k,  Теперь можно сказать, что строковая задача разрешения является языком над алфавитом  Σ . Например, задаче разрешения о существовании в графе пути длины не превосходящей соответствует язык PATH = { | 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(nk), где n — длина слова x, а k — некоторое не зависящее от x число.  Язык L распознается за полиномиальное время, если некоторый алгоритм A распознает  данный язык, причем время работы алгоритма на каждом слове длины n не больше O(nk). Рассмотренный ранее язык PATH, допускается за полиномиальное время. Нетрудно  построить алгоритм, который методом поиска в ширину за полиномиальное время находит  кратчайший путь между вершинами u и v в графе G, а затем сравнивает длину найденного  пути с данным в условии числом k. Если длина пути не превосходит k, алгоритм выдает 1 и  останавливается. В противном случае алгоритм зацикливается, не выдавая никакого  ответа. Ясно, что такой алгоритм допускает, но не распознает язык PATH. Однако легко  исправить описанный алгоритм таким образом, чтобы слова, не принадлежащие языку,  отвергались. Такой алгоритм допускает и распознает язык PATH. Стоит отметить, что  некоторые языки (например, для множества всех программ, заканчивающих свою работу)  имеют допускающий алгоритм, но не имеют распознающего. Определение класса задач P мы уже имеем. Дадим определение класса NP.  Неформально сложностной класс можно определить как семейство языков, для которых  распознающие алгоритмы имеют заданную меру сложности, например заданное время  работы. В теории существует множество сложностных классов. Один из них (P) мы уже  рассматривали. Есть также не менее важный класс PSPACE — состоящий из задач,  решаемых алгоритмами с использованием памяти полиномиального размера. Или класс  EXP, состоящий из задач, которые решаются за время O(2nk). Переформулируем  определение класса P: P = {L ⊂ {0,1}* | существует алгоритм A, распознающий L за  полиномиальное время.} На самом деле в данной ситуации нет разницы между языками  допускаемыми и распознаваемыми за полиномиальное время, о чем свидетельствует  следующая теорема. Теорема P = {L | L допускается за полиномиальное время}. Доказательство. Если язык распознается некоторым алгоритмом, то он и допускается тем же алгоритмом. Остается доказать, что если язык L допускается полиномиальным  алгоритмомA, то он и распознается некоторым (возможно, другим) полиномиальным  алгоритмом A . Пусть алгоритм существует константа c, для которой A допускает любое слово длины n из L, сделав не  более T = cnk шагов. С другой стороны слова не из L алгоритм не допускает (ни за какое  время).  A допускает язык L за время O(nk). Это значит, что  ′ ′ ′ Новый алгоритм A  моделирует работу алгоритма алгоритма, сравнивая его с известной границей T. Если за время T алгоритм A допускает  слово x, алгоритм A  также допускает это слово и выдает 1. Если же  A не допускает x за  указанное время, то алгоритм A  прекращает моделирование и отвергает слово (выдает 0).  Замедление работы за счет моделирования и подсчета шагов не так уж велико и оставляет  время работы полиномиальным.  A и считает число шагов этого  ′ Проверка принадлежности языку и класс NP Выше мы рассматривали задачу разрешения PATH. Эта задача оказалась полиномиальной  (и решается с помощью алгоритма поиска в ширину). Допустим, однако, что мы ничего не  знаем про поиск в ширину. Тогда задача PATH будет для нас трудной: видя граф G и  вершины u и v и зная число k, мы не будем знать, есть ли искомый путь, пока нам его не  покажут. Но если он нам станет известен, то мы можем легко проверить, что этот путь —  искомый. Именно такая ситуация имеет место для задач из класс NP. Гамильтонов цикл Задача поиска гамильтонова цикла в графе изучается уже более ста лет. Гамильтоновым  циклом в неориентированном графе G = (V, E) называется простой цикл, который  проходит через все вершины графа. Графы, в которых есть гамильтонов цикл,  называют гамильтоновыми. Задача о гамильтоновом цикле состоит в выяснении, имеет  ли заданный граф Gгамильтонов цикл. Формально говоря, HAM­CYCLE = { | 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 можно решить для любого  ′ ′ Теперь дадим формальное определение. Говорят, что язык L1 сводится за  полиномиальное время к языку L2 (запись: L1 ≤P L2), если существует такая  функция f: {0,1}* → {0, 1}*, вычислимая за полиномиальное время, что для  любого x ∈ {0, 1}*: x ∈ L1 равносильно f(x) ∈ L2. Функцию f называют сводящей  функцией, а полиномиальный алгоритм F, вычисляющий f, — сводящим алгоритмом.  Рисунок, приведенный выше, иллюстрирует данное определение сводимости.  Запись L1 ≤P L2 можно интерпретировать так: сложность языкаL1 не более чем  полиномиально превосходит сложность языка L2. Лемма Если язык L1 ⊂ {0, 1}* сводится за полиномиальное время к языку L2 ⊂ {0, 1}* и L2 ⊂ P,  то L1 ⊂ P. Доказательство. Пусть A2 — полиномиальный алгоритм, распознающий язык L2, а F —  полиномиальный алгоритм, сводящий язык L1 к языку L2. Построим алгоритм A1, который  будет за полиномиальное время разрешать язык L1, согласно нижеприведенной  иллюстрации, а именно: получив на вход x ∈ {0, 1}*, алгоритм A1 (с помощью алгоритма F) получает f(x) и с помощью алгоритма A2 проверяет, принадлежит ли слово f(x) языку L2.  Результат работы алгоритма A2 на основе f(x) и выдается алгоритмом A1 в качестве ответа. Определение полиномиальной сводимости гарантирует, что алгоритм A1 дает правильный  ответ; он полиномиален, поскольку полиномиальны алгоритмы F и A2. NP­полнота Понятие сводимости позволяет формализовать сравнение языков относительно их  трудности. Запись L1 ≤P L2 можно интерпретировать так: сложность языка L1 не более чем  полиномиально превосходит сложность языка L2. Наиболее трудны в этом смысле 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­полные задачи играют здесь центральную роль — дело в том, что полиномиальное время является, хоть и первым, но  достаточно хорошим приближением понятия «практической разрешимости задачи». Как уже было упомянуто ранее, определяющим источником данной статьи является [1].  Однако существует немало других интересных книг по данной тематике, заслуживающих  пристального внимания со стороны читателя. Среди них хотелось бы выделить [2], где  можно найти большое разнообразие NP­полных задач из самых различных областей.  Читателям, желающим подробнее ознакомиться с теорией сложности, на мой взгляд, будет  интересен подробный курс лекций [3], глубоко освещающий данную тематику. Литература 1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.:  МЦНМО, 2001. 2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи:  Пер. с. англ. — М.: Мир, 1982. 3. Oded Goldreich. Introduction to Complexity Theory — Weizmann Institute of Science,  Israel, 1999. Теория алгоритмов Теория сложности вычислений и сложностные классы задач Теоретический предел трудоемкости задачи Рассматривая некоторую алгоритмически разрешимую задачу, и анализируя один из  алгоритмов ее решения, мы можем получить оценку трудоемкости этого алгоритма в  худшем случае – fa()=O(g()). Такие же оценки мы можем получить и для других известных  алгоритмов решения данной задачи. Рассматривая задачу с этой точки зрения, возникает  резонный вопрос – а существует ли функциональный нижний предел для g() и если «да», то существует ли алгоритм, решающий задачу с такой трудоемкостью в худшем случае. Другая, более точная формулировка, имеет следующий вид: какова оценка сложности  самого «быстрого» алгоритма решения данной задачи в худшем случае? Очевидно, что это  оценка самой задачи, а не какого либо алгоритма ее решения. Таким образом, мы приходим к определению понятия функционального теоретического нижнего предела трудоемкости  задачи в худшем случае: = min {  ( (D)) } Если мы можем на основе теоретических рассуждений доказать существование и получить  оценивающую функцию, то мы можем утверждать, что любой алгоритм, решающий данную  задачу работает не быстрее, чем с оценкой  в худшем случае:  (D) =  () Приведем ряд примеров: Задача поиска максимума в массиве A=(a1,…,an) – для этой задачи, очевидно должны быть просмотрены все элементы, и = (n). Задача умножения матриц ­ для этой задачи можно сделать предположение, что  необходимо выполнить некоторые арифметические операции со всеми исходными  данными, теоретическое обоснование какой–либо другой оценки на сегодня не известно,  что приводит нас к оценке =Q (). Отметим, что лучший алгоритм умножения матриц имеет  оценку Q (). Расхождение между теоретическим пределом и оценкой лучшего известного  алгоритма позволяет предположить, что либо существует, но еще не найден более быстрый  алгоритм умножения матриц, либо оценка Q () должна быть доказана, как теоретический  предел. Сложностные классы задач В начале 1960­х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости  данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи  могут быть решены на ЭВМ за реальное время? Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964), и Эдмнодса (Jack  Edmonds, 1965), где были введены сложностные классы задач. 1) Класс P (задачи с полиномиальной сложностью) Задача называется полиномиальной, т.е. относится к классу P, если существует константа k и алгоритм, решающий задачу с (n)=O(), где n ­ длина входа алгоритма в битах n = |D| [6]. Задачи класса P – это интуитивно, задачи, решаемые за реальное время. Отметим следующие преимущества алгоритмов из этого класса: для большинства задач из класса P константа k меньше 6; класс P инвариантен по модели вычислений (для широкого класса моделей); класс P обладает свойством естественной замкнутости (сумма или произведение  полиномов есть полином). Таким образом, задачи класса P есть уточнение определения «практически разрешимой»  задачи. 2) Класс NP (полиномиально проверяемые задачи) Представим себе, что некоторый алгоритм получает решение некоторой задачи –  соответствует ли полученный ответ поставленной задаче, и насколько быстро мы можем  проверить его правильность? Рассмотрим, например задачу о сумме: Дано N чисел – А = (a1,…an) и число V. Задача: Найти вектор (массив) X=(x1,…,xn), xiє{0,1}, такой, что aixi = V. Содержательно: может ли быть представлено число V в виде суммы каких­либо элементов  массива А. Если какой­то алгоритм выдает результат – массив X, то проверка правильности этого  результата может быть выполнена с полиномиальной сложно­стью: проверка  aixi = V  требует не более Q (N) операций. Формально: Dє, |D|=n поставим в соответствие сертификат Sє , такой что |S|=O () и  алгоритм  =  (D,S), такой, что он выдает «1», если решение правильно, и «0», если решение  неверно. Тогда задача принадлежит классу NP, если F (  )=O ( ). Содержательно задача относится к классу NP, если ее решение некоторым алгоритмом  может быть быстро (полиномиально) проверено. Проблема P = NP После введения в теорию алгоритмов понятий сложностных классов Эдмондсом (Edmonds, 1965) была поставлена основная проблема теории сложности – P = NP ? Словесная  формулировка проблемы имеет вид: можно ли все задачи, решение которых проверяется с  полиномиальной сложностью, решить за полиномиальное время ? Очевидно, что любая задача, принадлежащая классу P, принадлежит и классу NP, т.к. она  может быть полиномиально проверена – задача проверки решения может состоять просто в повторном решении задачи. На сегодня отсутствуют теоретические доказательства как совпадения этих классов  (P=NP), так и их несовпадения. Предположение состоит в том, что класс P является  собственным подмножеством класса NP, т.е. NP \ P не пусто – рис 6.1 Класс NPC (NP – полные задачи) Понятие NP – полноты было введено независимо Куком (Stephen Cook, 1971) и Левиным  (журнал «Проблемы передачи информации», 1973,т.9, вып. 3) и основывается на понятии  сводимости одной задачи к другой. Сводимость может быть представлена следующим образом: если мы имеем задачу 1 и  решающий эту задачу алгоритм, выдающий правильный ответ для всех конкретных  проблем, составляющих задачу, а для задачи 2 алгоритм решения неизвестен, то если мы  можем переформулировать (свести) задачу 2 в терминах задачи 1, то мы решаем задачу 2. Таким образом, если задача 1 задана множеством конкретных проблем  , а задача 2 –  множеством, и существует функция  (алгоритм), сводящая конкретную постановку задачи  2 ( ) к конкретной постановке задачи 1(): , то задача 2 сводима к задаче 1. Если при этом () = O(), т.е. алгоритм сведения принадлежит классу P, то говорят, что  задача 1 полиномиально сводится к задаче 2. Принято говорить, что задача задается некоторым языком, тогда если задача 1 задана  языком L1, а задача 2 – языком L2, то полиномиальная сводимость обозначается  следующим образом: L2 =< pL1. Определение класса NPC (NP­complete) или класса NP­полных задач требует выполнения  следующих двух условий: во­первых, задача должна принадлежать классу NP (L є NP), и,  во­вторых, к ней полиномиально должны сводиться все задачи из класса NP (Lx=< pL, для  каждого Lx є NP), что схематично представлено на рис 6.2. Для класса NPC доказана следующая теорема: Если существует задача, принадлежащая  классу NPC, для которой существует полиномиальный алгоритм решения (F = O()), то  класс P совпадает с классом NP, т.е. P=NP. Схема доказательства состоит в сведении любой задачи из NP к данной задаче из класса  NPC с полиномиальной трудоемкостью и решении этой задачи за полиномиальное время  (по условию теоремы). В настоящее время доказано существование сотен NP–полных задач, но ни для одной из  них пока не удалось найти полиномиального алгоритма решения. В настоящее время  исследователи предполагают следующее соотношение классов, показанное на рис 6.3 – P   NP, то есть NP \ P  0, и задачи из класса NPC не могут быть решены (сегодня) с  полиномиальной трудоемкостью. Примеры NP – полных задач 1 Задача о выполнимости схемы Рассмотрим схему из функциональных элементов «и», «или», «не» с n битовыми входами и одним выходом, состоящую не более, чем из O() элементов – рис 6.4 Будем понимать под выполняющим набором значений из множества {0,1} на входе схемы,  такой набор входов – значения x1,…,xn, при котором на выходе схемы будет значение «1». Формулировка задачи – существует ли для данной схемы выполняющий набор значений  входа. Очевидно, что задача принадлежит классу NP – проверка предъявленного  выполняющего набора не сложнее количества функциональных элементов, и следовательно не больше чем O(). Это была одна из первых задач, для которой была доказана ее NP полнота, т.е. любая  задача из класса NP полиномиально сводима к задаче о выполнимости схемы. Решение этой задачи может быть получено перебором всех  возможных значений входа с  последующей проверкой на соответствие условию выполняющего набора. В худшем случае  придется проверить все возможные значения входа, что приводит к оценке  Для этой, как и для всех других NP–полных задач не известен полиномиальный алгоритм решения. 2 Задача о сумме Уже рассмотренная задача о сумме также является NP–полной, отметим, что если  количество слагаемых фиксировано, то сложность задачи является полиномиальной, так  как: для 2­х слагаемых  для 3­х слагаемых  Однако в общем случае придется перебирать  различных вариантов, так как по  биномиальной теореме , а при a=b=1, имеем:  3 Задача о клике Пусть дан граф G = G(V,E), где V – множество из n вершин, а E – множество ребер. Будем  понимать под кликой максимальный по количеству вершин полный подграф в графе в G. Задача состоит в определении клики в заданном графе G Поскольку в полном графе на m вершинах имеется m(m­1)/2 ребер, то проверка, является  ли данный граф полным, имеет сложность O (). Очевидно, что если мы рассматриваем  подграф с m вершинами в графе G с вершинами (m < n), то всего существует  различных  подграфов. Если в задаче о клике количество вершин клики фиксировано, то  перебирающий алгоритм имеет полиномиальную сложность: Однако в общем случае придется проверять все подграфы с количеством вершин m = (2, n)  на их полноту и определить максимальное значения m для которого в данном графе G  существует полный подграф, что приводит к оценке в худшем случае: