Алгоритмы на языке «разделяй и властвуй». Понятие о классах r и np, np-полных задачах

Дополнительные термины и определения: -

• 
  
  NP-жесткий - если XеЕсли NP попадает в X, то проблема X как минимум разрешима в NP, т. е. любая задача в NP трудноразрешима (если P! = NP, то XP не актуален).
  
• 
  
  Редукция — это процесс преобразования входных данных задачи A в эквивалентные входные данные задачи B с использованием алгоритма времени умножения. Эквивалентность означает, что задачи A и B должны давать одинаковый ответ (да или нет) для ввода и модифицированного ввода. Существование алгоритма приведения из A в B подразумевает следующее:
  

1. Если БеЕсли П, то АеP (вы можете свести A к B за полиномиальное время и решить B за полиномиальное время. Комбинация этого дает алгоритм полиномиального времени для A)
2. Если БеЕсли НП, то АеНП
3. Если A NP-сложно, то B NP-трудно. A сводится к B с возрастанием времени, и если B не является NP-трудным, то BB NP-NP-трудным, и поэтому AеNP-NP-hard означает, что он противоречит гипотезе (A-NP-hard).

• 
  
  NP-полнота - если XеЗадача X является NP-полной, если NP и X NP-сложны.
  

Докажите, что задача NP-полная.

Доказательство полноты задачи включает 2 шага. Сначала нам нужно показать, что задача NP-трудна, а затем нужно показать, что она NP-трудна. Шаги можно объяснить следующим образом:
Шаг 1 - ХеПокажи НП. Найдите недетерминированный алгоритм для x. Но практический способ состоит в том, чтобы выполнить мультипликативную проверку времени для X, если представлено потенциальное решение.
Шаг 2. Показать X несложно. Сведение известной NP-задачи к X. Итак, на рис. 3 мы видим, что X NP-сложно.

Равна ли эта задача короткому P и NP сложному классу?P-класс - это набор задач, которые могут быть решены "быстро" ("Мгновенно") компьютером. Сюда входят основы (базис) арифметических действий, сортировка списков, поиск данных в таблице.К NP-классу относится задача, где можно быстро проверить правильность ответа. Например: допустим, у вас есть монеты номиналом 2, 3, 5, 6 и 7 сумов, и вы хотите оплатить покупку на сумму 21 сум. Можно ли из них собрать монеты общей суммой 21 сум?Для получения ответа на эту задачу необходимо выбрать любой вариант, если мы хотим доказать, что задача не имеет решения, в общем случае должны быть выбраны все возможные варианты. Если увеличить количество монет несколькими способами, решение будет выглядеть совершенно несогласованным. В этом случае для удобства проверки результата суть всей «проблемы тысячи лет» выражается (определяется) так: Равны ли классы P и NP? Если легко проверить правильность решения задачи, то может ли легко решить и саму задачу?Многие специалисты считают, что ответ отрицательный (отрицательный), но доказать это еще никому не удалось.Если П =NP, то человечество резко повернется к криптографии.

NP-полнотапроблема
Большинство задач, представляющих практический интерес, представляют собой полиномиальные (работающие за полиномиальное время) алгоритмы. То есть на входе длины n время работы алгоритма не превышает O(nk) для константы k (не зависящей от длины входа). Не для каждой задачи существует алгоритм решения, удовлетворяющий этому свойству. Некоторые задачи вообще не могут быть решены никаким алгоритмом. Классическим примером такой проблемы является «проблема остановки» (знание того, остановится ли данная программа на данном входе). Более того, есть задачи, для которых есть алгоритм, решающий их, любой такой алгоритм требует много времени — его время работы не может быть O(nk) для любого фиксированного числа k.
Если мы хотим провести грубую, но формальную границу между практическими алгоритмами и алгоритмами, представляющими только теоретический интерес, то на первое место выходит класс алгоритмов с полиномиальным временем. Рассмотрим класс задач, называемый NP-полным. Полиномиальные алгоритмы для этих задач найдены не были, но существование таких алгоритмов не доказано. Изучение проблем NP связано с вопросом, называемым «P = NP». Этот вопрос был задан в 1971 году и сейчас считается одной из самых сложных проблем теории вычислений.
Зачем программисту знать о NP-полных задачах? Если можно доказать его полноту для любой NP-полноты, есть основания полагать, что она почти неразрешима. В этом случае лучше потратить время на построение приближенного алгоритма, чем продолжать поиск быстрого алгоритма, который точно его решит.
Полиномиальное время. Абстрактные вопросы
Как упоминалось выше, концепция многоразрешимых (полиномиальных) задач на самом деле является усовершенствованием идеи разрешимых задач. Чем объясняется это соглашение? Во-первых, расширенные алгоритмы, используемые на практике, обычно очень быстры. Второе соображение класса полиномиальных алгоритмов состоит в том, что размер этого класса почти не зависит от выбора конкретной вычислительной модели. Например, класс задач, решаемых за увеличенное время на машине с произвольным доступом (ОЗУ), соответствует классу полиномиально разрешимых задач на машинах Тьюринга. Класс тот же для модели параллельных вычислений,количество процессоров, ограниченный входным полиномом длины. В-третьих, класс полиномиальных разрешимых задач обладает естественными замкнутыми свойствами. Например, композиция из двух алгоритмов также работает за полиномиальное время. Это потому, что сумма, произведение и композиция многочленов являются многочленами.
Ниже представлена ​​абстрактная модель задачи расчета. Назовем ее абстрактной задачей, Q — произвольное бинарное отношение между элементами двух множеств: I — множество условий, S — множество решений. Например, в задаче нахождения кратчайшего пути между двумя заданными вершинами неориентированного графа G=(V,E) условие (элемент I) состоит из трех элементов, графа и двух ребер, а решение (элемент C) — искомый путь в этом графе Последовательность вершин, составляющих l.
В теории NP-полноты рассматриваются только задачи решения — задачи, требующие ответа «да» или «нет» на конкретный вопрос. Формально члены множества I можно рассматривать как функцию, соответствующую множеству {0,1}. Например, используя граф G=(V,E), заданный задачей поиска кратчайшего пути в графе G=(V,E), два узла u, vеВа натуральные k целых чисел между вершинами u и v не превосходят и решают вопрос о том, есть ли путь в графе G или нет.
Задачи оптимизации — это задачи, в которых необходимо максимизировать или минимизировать определенное количество ценности. Прежде чем задавать вопросы об NP-полноте, такие проблемы необходимо преобразовать в проблемы решения. Так, например, в задаче поиска кратчайшего пути в графе мы перешли от решения задачи оптимизации к задаче перестановок и добавили ограничение на длину пути. Если после преобразования NP завершаетсяесли возникнет проблема, где также определяется сложность исходной задачи. Представление данных
Прежде чем вводить входные данные (т. е. элемент множества I) в алгоритм, необходимо договориться о том, как их представить в «компьютерном» виде. Мы предполагаем, что исходные данные закодированы последовательностью битов. Формально говоря, представление элементов множества S — это отображение множества S на наборы e-битных строк. Например, (0, 1, 2, 3,...) - целые числа, обычно (0, 1, 10, 11, 100,...) - представлены битовыми строками.
Размещая заданные данные, мы преобразуем абстрактную задачу в строковые данные, которые являются входными данными для строковых данных, битовой строкой, представляющей исходные данные задачи. Если входные данные (строка битов) имеют n-длину, время работы алгоритма O(T(n)) - тогда можно сказать, что алгоритм решает проблему со строками за время O(T(n)) . Если k постоянно и существует алгоритм, решающий эту задачу за время O(T(n)), то задача о струнах называется полиномиальной. Класс сложности P — это все линейные задачи, которые можно решить за полиномиальное время, то есть за время O(nk), где k не зависит от входных данных.
Понятие полиномиальной абстрактной задачижелая узнать, мы сталкиваемся с возможностью представления различной информации.
Для каждого заданного набора e мы получаем строковую задачу абстрактной задачи Q с входами I.
Однако на практике (за исключением «дорогих» методов представления, таких как система счисления с основанием 1), методы естественного представления обычно эквивалентны, поскольку они могут быть преобразованы друг в друга многими способами. Если существует полиномиальный алгоритм A, то функция f:{0,1}*→{0,1}* вычисляется за полиномиальное время, то есть для любого xеf(x) для {0,1}* дает результат.
Для необязательной абстрактной задачи мы рассматриваем множество условий I. Элементы e1 и e2 множества I называются полиномиально связанными, если два вычислимых за полиномиальное время f12(e1(i)) = e2(i) и f21(e2(i)) = e1(i) , iеЕсли есть функции I. В таких случаях не имеет значения, с каким из двух элементов связан полином.

P, NP, NP-полные отношения между классами, NP-жесткие, P≠NP и P=NP.
Проблема NP-полноты — в теории алгоритмов задача с ответом «да» или «нет» в NP-классе может быть адаптирована к другой задаче того же класса за полиномиальное время (то есть степень зависимость исходных данных от размера осуществляется с помощью операций, не превышающих некоторого полинома).
Таким образом, NP-полные задачи в определенном смысле образуют набор «типичных» задач класса NP: если для некоторых из них найден «быстрый» алгоритм решения, то может быть решена любая другая задача класса NP. таким же образом можно решить.
Формальное определение
Алфавит — это любой конечный набор символов (например, {0, 1} или {a, b, c}). Множество всех слов, образованных из произвольного ∑-алфавита (письменных строк, состоящих из символов этого алфавита), обозначается ∑*.
Произвольный язык L, порожденный с помощью алфавита ∑, является подмножеством L множества ∑^*, то есть L⸦∑^*.

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

∑ над алфавитом и - быть двумя языками. Язык (по Карпу) называется редукцией к языку L2, если существует функция, вычисляемая за полиномиальное время, то она обладает следующим свойством: : xеL1, ,если и только если. Укорочение запястья определяется как L1≤pL2.
Если любой язык из NP сводится к нему, то такой язык называется NP-полным. Язык называется NP-совершенным, если он NP-труден и сам принадлежит классу NP.
Тот факт, что проблема A сводится к проблеме B, означает, что проблема A «более сложна», чем проблема B (поскольку, если мы решаем проблему B, это означает, что проблема A также решена). Таким образом, в класс NP-трудностей входят как задачи, относящиеся к NP, так и задачи, «более сложные» для них (т. е. задачи, которые можно свести к задачам, относящимся к NP). Класс NP включает NP-полные задачи и задачи, которые «легче» их (т. е. задачи, сводящиеся к NP-полным задачам).
Из определения следует, что если найден алгоритм, решающий NP-полную задачу за полиномиальное время, то все NP-полные задачи помещаются в класс P, т. е. решаются за полиномиальное время.