Труднорешаемые задачи Последовательный анализ вариантов (стр. 3 из 4)
2.1 Последовательный анализ вариантов
Выше рассматривались вопросы построения активного расписания, допустимого относительно ориентированного или смешанного графа. Было Сказано, что не более чем за
элементарных действий можно построить допустимое расписание либо установить невозможность построения такого расписания.Если на каждом шаге алгоритма 2 рассматривать все возможные варианты выбора вершины i, в которую не заходит ни одна исходящая из: неотмеченной вершины дуги, то можно получить все множество P(G={G1,G2….G} бесконтурных графов порождаемых графом G = (Q, U, V). Задачу можно решить в результате построения активных расписаний, допустимых относительно графов
, и выбора среди них расписания S* минимизирующего значение F(s)-Трудоемкость полного перебора всех активных расписаний задачи 
может бытьограничена величиной 
при условии, что для вычисления функции F(s) требуется не более 
элементарных действий.К сожалению, мощность множества P(G)растет в обшей случае экспоненциально с ростом параметров задачи n и М. Например, для задачи
значение 
равно n!. Граф 
при этом является полным не ориентированным: 
и q=n. Рост значений |v| и показан в табл. 1Таблица 1.
Сокращение числа перебираемых расписании можно обеспечить методом последовательного анализа вариантов. Для организации целенаправленного перебора графов множества P(G)будем использовать процедуру последовательного разбиения множества P(G) на подмножества.
При этом подмножествоP(G) сначала разбивается vaподмножества P(G1), P(G2)…… P(Gk),где Gk , k=1,h- графы, получаемые из
в результате замены одного или нескольких ребер V дугами. Затем одно из множеств P(Gk), например P(Gl), в свою очередь разбивается на подмножества P(Gh+1),P(Gh+2),..., P(Gh+p),результате получаем разбиение исходного множестваЭтот процесс удобно представлять „растущим" выходящим деревом
где Zm - множество его вершина.Множество всех конечных вершин дерева (Zm, Wm) будем обозначать через Zm. При выполнении условия а) получаем точное значение f(C'). Нетрудно видеть, что из условия б) следует соотношение
для любого графа 
. При выполнении условия в) существует граф 
такой, что 
. Следовательно, при поиске оптимального расписания граф G1 можно исключить из рассмотрения, если условие б) или в) выполняется.3. Псевдополиномиальное сведение задач и NP-трудные в сильном смысле задачи
Наряду с разделением задач на NP-трудные и полиномиально разрешимые, NP-трудные задачи, в свою очередь, подразделяются на NP-трудные в сильном смысле задачи и задачи, имеющие псевдополиномиальные алгоритмы решения.
Алгоритм решения задачи Π называется псевдополиномиальным, если его временная сложность не превосходит некоторого полинома от двух переменных Lengthn[I] и Maxц[I] для любого примера I задачи Π. Соответствующая задача называется псевдополиномиалъно разрешимой.
Нетрудно заметить, что любой полиномиальный алгоритм является одновременно и псевдополиномиальным. Кроме того, ни одна из NP-трудных задач, не имеющая числовых параметров, не может иметь псевдополиномиального алгоритма решения, если
В противном случае такая задача имела бы полиномиальный алгоритм решения, поскольку
для любого ее примера. Аналогично, если для задачи Π существует такой полином, что для 
любого 
то Π, удучи NP-трудной, не может быть псевдополиномиально разрешимой.Таким образом, существуют NP-трудные задачи, которые не могут иметь даже псевдополиномиальных алгоритмов решения. Такие задачи образуют множество так называемых NP-трудных в сильном смысле задач. Для формализации понятия NP-трудной в сильном смысле задачи введем определение псевдополиномиальной сво димости задач распознавания.
Пусть пары функций (Lengthn, Maxц) и (Lengthu', Maxц>) сопоставлены задачам Π и Π' соответственно.
Говорят, что задача распознавания Π псевдополиномиалъно сводится к задаче распознавания Π', если существует словарная функция Φ, переводящая задачу Π в задачу Π' и удовлетворяющая следующим условиям:
(а) для любого примера 
соотношение 
выполняется тогда и только тогда, когда выполняется
(б) временная сложность вычисления функции Φ не превосходит некоторого полинома qот двух переменных Lengthn[I] и Maxп [I ] ;
(в) существуют такие полиномы qiи qi, что для любого I
Задача распознавания Π называется NP-трудной в сильном смысле, если существует NP-трудная задача распознавания Π, которая псевдополиномиально сводится к Π и для любого
Поскольку любая задача псевдополиномиально сводится к себе, то любая NP-трудная задача, удовлетворяющая условию (1.3), является NP-трудной в сильном смысле. Кроме того, любая NP-трудная в сильном смысле задача является NP-трудной, и ни одна из NP-трудных в сильном смысле задач не может иметь псевдополиномиального алгоритма решения, если
Понятие псевдполиномиальной сводимости транзитивно. Поэтому для доказательства NP-трудности в сильном смысле некоторой задачи достаточно псевдополиномиально свести к ней некоторую NP-трудную задачу.
Задача распознавания Π называется NP-полной в сильном смысле, если Π
и Π является NP-трудной в сильном смысле.Экстремальная комбинаторная задача называется NP-трудной в сильном смысле, если сопоставленная ей задача распознавания NP-трудна в сильном смысле.
Примеры NP-трудных задач
Ниже приведены формулировки NP-трудных задач, которые в дальнейшем используются при доказательстве NP-трудности задач оптимального планирования.
Разбиение:
Заданы целые положительные числа aл, aо,..., aги A такие,
Требуется определить, существует ли множество
такое что 
4. Использование NP-трудных задач
В настоящее время большое распространение получили криптосистемы с открытыми ключами, характерным свойством которых является то, что знание алгоритма не даёт дополнительных преимуществ при взломе, в отличие от симметричных систем, которые легко взламываются, если знать, по какому базовому правилу они работают. Типичным и самым популярным на данный момент примером системы с открытым ключом является RSA (алгоритм был опубликован в 1977 Ривестом, Шамиром, Эдлманом в MIT). Эта система проста в использовании, и, что более важно, сложна во взломе. Однако до сих пор остаётся открытым вопрос – относится ли задача факторизации, на которой базируется алгоритм RSA, к классу полиномиально разрешимых P или же к классу NP-трудных задач. Задача Р versus NP частично обязана своей значимостью пользующейся успехом теории завершенности NP и частично теории криптографии. Алгоритм удовлетворимости, будучи истинно эффективным алгоритмом по отношению к задаче завершенности NP, с одной стороны, мог бы вызвать к жизни целый ряд полезных алгоритмов для решения многих практических вычислительных задач в промышленности, однако, с другой стороны, такой алгоритм разрушил бы безопасность финансовых и иных сделок, широко использующих Интернет. Не сегодня-завтра может оказаться, что задача факторизации не является NP-трудной и более того, может найтись полиномиальный алгоритм её решения. В этом случае понадобятся совершенно другие методы криптографии. В данной работе я покажу некоторые криптографические методы, основанные на сложности широко известной NP-трудной задачи, задачи о рюкзаке(Knapsack problem)