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

Формальное определение

Гипотеза P ≠ NP

Вопрос о совпадении классов P и NP уже более 30 лет является открытой проблемой . Научное сообщество склоняется к отрицательному ответу на этот вопрос - в этом случае решать NP-полные задачи за полиномиальное время не удастся.

Примеры NP-полных задач

См. также

• Список NP-полных задач (англ.) русск.

Напишите отзыв о статье "NP-полная задача"

Примечания

Литература

• Томас Х. Кормен и др. Глава 34. NP-полнота // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М .: «Вильямс» , 2006. - С. 1296. - ISBN 0-07-013151-1 .

Ссылки

• (англ.)
• (англ.)

Считаются лёгкими Предполагаются сложными Считаются сложными

NP-полные задачи Исследование операций :Оптимизация :Комбинаторная оптимизация Максимизационная задача укладки (упаковки) Теория графов теория множеств Алгоритмические задачи Логические игры и головоломки См. также

Отрывок, характеризующий NP-полная задача

Курьер, подскакавший к замку на потной тройке, впереди государя, прокричал: «Едет!» Коновницын бросился в сени доложить Кутузову, дожидавшемуся в маленькой швейцарской комнатке.
Через минуту толстая большая фигура старика, в полной парадной форме, со всеми регалиями, покрывавшими грудь, и подтянутым шарфом брюхом, перекачиваясь, вышла на крыльцо. Кутузов надел шляпу по фронту, взял в руки перчатки и бочком, с трудом переступая вниз ступеней, сошел с них и взял в руку приготовленный для подачи государю рапорт.
Беготня, шепот, еще отчаянно пролетевшая тройка, и все глаза устремились на подскакивающие сани, в которых уже видны были фигуры государя и Волконского.
Все это по пятидесятилетней привычке физически тревожно подействовало на старого генерала; он озабоченно торопливо ощупал себя, поправил шляпу и враз, в ту минуту как государь, выйдя из саней, поднял к нему глаза, подбодрившись и вытянувшись, подал рапорт и стал говорить своим мерным, заискивающим голосом.
Государь быстрым взглядом окинул Кутузова с головы до ног, на мгновенье нахмурился, но тотчас же, преодолев себя, подошел и, расставив руки, обнял старого генерала. Опять по старому, привычному впечатлению и по отношению к задушевной мысли его, объятие это, как и обыкновенно, подействовало на Кутузова: он всхлипнул.
Государь поздоровался с офицерами, с Семеновским караулом и, пожав еще раз за руку старика, пошел с ним в замок.
Оставшись наедине с фельдмаршалом, государь высказал ему свое неудовольствие за медленность преследования, за ошибки в Красном и на Березине и сообщил свои соображения о будущем походе за границу. Кутузов не делал ни возражений, ни замечаний. То самое покорное и бессмысленное выражение, с которым он, семь лет тому назад, выслушивал приказания государя на Аустерлицком поле, установилось теперь на его лице.
Когда Кутузов вышел из кабинета и своей тяжелой, ныряющей походкой, опустив голову, пошел по зале, чей то голос остановил его.
– Ваша светлость, – сказал кто то.
Кутузов поднял голову и долго смотрел в глаза графу Толстому, который, с какой то маленькою вещицей на серебряном блюде, стоял перед ним. Кутузов, казалось, не понимал, чего от него хотели.
Вдруг он как будто вспомнил: чуть заметная улыбка мелькнула на его пухлом лице, и он, низко, почтительно наклонившись, взял предмет, лежавший на блюде. Это был Георгий 1 й степени.

На другой день были у фельдмаршала обед и бал, которые государь удостоил своим присутствием. Кутузову пожалован Георгий 1 й степени; государь оказывал ему высочайшие почести; но неудовольствие государя против фельдмаршала было известно каждому. Соблюдалось приличие, и государь показывал первый пример этого; но все знали, что старик виноват и никуда не годится. Когда на бале Кутузов, по старой екатерининской привычке, при входе государя в бальную залу велел к ногам его повергнуть взятые знамена, государь неприятно поморщился и проговорил слова, в которых некоторые слышали: «старый комедиант».
Неудовольствие государя против Кутузова усилилось в Вильне в особенности потому, что Кутузов, очевидно, не хотел или не мог понимать значение предстоящей кампании.
Когда на другой день утром государь сказал собравшимся у него офицерам: «Вы спасли не одну Россию; вы спасли Европу», – все уже тогда поняли, что война не кончена.
Один Кутузов не хотел понимать этого и открыто говорил свое мнение о том, что новая война не может улучшить положение и увеличить славу России, а только может ухудшить ее положение и уменьшить ту высшую степень славы, на которой, по его мнению, теперь стояла Россия. Он старался доказать государю невозможность набрания новых войск; говорил о тяжелом положении населений, о возможности неудач и т. п.
При таком настроении фельдмаршал, естественно, представлялся только помехой и тормозом предстоящей войны.

словами, существует ли такое назначение регистров 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), именно, имеет место следующая теорема.

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

Все приведённые ранее примеры 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 .

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

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

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

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

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

Примеров экспоненциальных алгоритмов успешно используемых на практике мало. Более того даже для полиномиальных алгоритмов представляют практический интерес алгоритмы сложность которых имеет порядок 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. Недетерминированная машина Тьюринга, её отличие от детерминированной машины Тьюринга.

– множество задач

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

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

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

В исследованиях проблемы P ¹NP важное положение занимает понятие полиномиальная сводимость , используя ранее введенное понятие (и обозначение) сводимости - задача A полиномиально сводима к задаче B , если A μp(n)B для некоторого полинома p(n). Задача A называется C025A>_____NP-полной , если A Î NP и для любой другой задачи B Î NP имеет место полиномиальная сводимость B к A. Честь быть «первой» NP-полной задачей выпала на долю задачи распознавания выполнимости формул булевой логики. Кук С.А. показал как формулами булевой логики можно описать работу любой программы недетерминированного вычислителя и на этой основе доказал полиномиальную сводимость любой NP-задачи к задаче о выполнимости. Методом (полиномиального) сведения на сегодняшний день доказана NP-полнота обширнейшего семейства задач в различных областях: в булевой логике, в теории графов, в арифметике, при разработке сетей, в теории множеств и разбиений, при хранении поиске информации, при планировании вычислительных процессов, в математическом программировании, в алгебре и теории чисел, при создании игр и головоломок, в теории автоматов и языков, при оптимизации программ, в биологии, в химии, физике и т.п.

Оригинальные идеи Кука оказались удивительно плодотворными. Они позволили свести много разнообразных вопросов о сложности в единый вопрос: «Верно ли, что NP- полные задачи труднорешаемы?»

15.Абстрактные типы данных: последовательность, множество, отображение

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

§ множеством возможных значений этого типа,

§ и набором операций со значениями этого типа.

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

§ способ представления значений этого типа,

§ и реализацию операций со значениями этого типа.

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

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

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

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

В исследованиях по абстрактным типам данных уже на раннем этапе была осознана важная роль понятия «параметризация типа ». Действительно, например АТД «Стек» не зависит от типа элементов стека, но реализовать этот АТД указанием на «элементы какого-то одинакового типа» невозможно. В язык программирования Ada соответствующие средства конструирования параметризованных типов данных были включены изначально, а в современных «практических языках программирования» какие средства появились только со времен появления разработки по STL-библиотеке . На сегодня понятие «обобщенное программирование» занимает значимое положение в практическом программировании благодаря включению в «практические языки программирования» средств конструирования параметризованных типов данных (шаблоны, template, generic) . 37

Всё вышесказанное означает, что с методологической и теоретической точки зрения необходимо более детальное точное определение понятия «абстрактный тип данных». В теории понятие «абстрактный _____・8тип данных» обычно определяется как многосортная (многоосновная) алгебраическая система , в которой дополнительно к множеству возможных значений (носителю) и набору операций над такими значениями выделены понятия:

§ Сорт и сигнатура – эти понятия позволяют расклассифицировать и элементы носителя и операции с ними по их типам (для операций - по типам их аргументов и возвращаемого значения).

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

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

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

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

2.1. Последовательность (Sequence).

Множество возможных значений – конечные последовательности элементов

одинакового типа.

Набор операций:

§ Вставить элемент в последовательность.

§ Удалить элемент из последовательности.

§ Посмотреть – функция, возвращающая значение элемента последовательности. Разновидности этого вида АТД различаются способом доступа к элементам последовательности и ограничениями на место вставки и удаления элементов. Для АТД этого вида стек (stack) , очередь (queue) и дек (deque от Double Ended Queue - двусторонняя очередь) характерно разрушающее чтение , т.к. доступ к элементам (для всех трех операций) ограничен одним из концов последовательности и операцию «посмотреть другой элемент» можно выполнить, только удалив мешающие этому элементы. Для АТД файл (file) и линейный список (linear list) ограничения на доступ обеспечивают неразрушающее чтение , поэтому особое значение имеет (производная) операция просмотра последовательности . Ограничения на доступ к элементам последовательности естественно отражаются на семантике основных операций. Последовательный доступ основан на понятии текущая позиция и допускает перемещение (навигацию) к одному (или к обоим) из концов последовательности и к соседней позиции (слева, справа или к обеим) относительно текущей. Место применения основных операций в этом случае обычно привязывается к текущей позиции. Прямой (позиционный, произвольный) доступ основанна глобальном Понятии позиция элемента в последовательности и обеспечивает непосредственный доступ к элементу, если известна его позиция. Например, в АТД динамический вектор (dynamic array, vector) , позиция – это индекс элемента. Но в других реализациях других видов последовательностей идентификатор позиции может быть реализован иначе.

Понятия «номер» и «позиция» элемента – близкие, но могут не совпадать:

§ Номер - это собственно порядковый номер элемента в последовательности. Но

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

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

Для АТД «Последовательность» представляют интерес дополнительные операции вида:

сцепить две последовательности, расцепить на две последовательности. Например, в АТД строка (string) такого вида операции фактически являются основными. Для различных видов АТД «Последовательность» достижима различающаяся эффективность реализации различных операций. Например, если реализация предлагает эффективный прямой доступ к элементам последовательности, то скорее всего – время 39 выполнения операции вставки в середине последовательности оставляет желать лучшего.

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

2.2. Множество (Set).

¨ Множество возможных значений – конечные множества элементов одинакового типа.

¨ Набор операций:

§ Вставить элемент во множество.

§ Удалить элемент из множества.

§ Принадлежать – функция, возвращающая значение true, если элемент

принадлежит множеству.

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

2.3. Словарь (Dictionary, Map), другое название – ассоциативный массив

.

¨ Множество возможных значений – конечные множества элементов одинакового типа, вида , где Key – уникальный ключ элемента, Value - собственно значение.

¨ Набор операций:

§ Вставить элемент (с ключом) во множество.

§ Удалить элемент (заданный ключом) из множества.

§ Найти элемент – функция, возвращающая по ключу значение элемента или «пустое» значение, если элемента с таким ключом нет во множестве. АТД «Словарь» - это специализированный вариант понятия (хранимое) отображение (ключей в значения), широко используемый в практическом программировании. Но для некоторых предметных областей возможно более удобным окажется оформление АТД «Отображение» (Mapping) , более близкое классическому математическому определению

Похожая информация.

Голосование: 38, 4

Введение

Большинство задач, интересных с практической точки зрения, имеют полиномиальные (работающие за полиномиальное время) алгоритмы решения. То есть время работы алгоритма на входе длины 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-полных задач из самых различных областей. Читателям, желающим подробнее ознакомиться с теорией сложности, на мой взгляд, будет интересен подробный курс лекций , глубоко освещающий данную тематику.

Литература

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

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

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

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).

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

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