Задачи, NP-трудные в сильном смысле

По дисциплине «Алгоритмы с оценками»

На тему «Труднорешаемые задачи. Последовательный анализ вариантов»

 

Содержание

Введение

1. Задачи, NP-трудные в сильном смысле

1.1. Обслуживание требований без задержек

2.Алгоритм

2.1 Последовательный анализ вариантов

Псевдополиномиальное сведение задач и NP-трудные в сильном смысле задачи

Использование NP-трудных задач

Заключение

Библиографический список

Введение

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

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

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

Задачи, NP-трудные в сильном смысле

 

Приводятся примеры доказательств NP-трудности в сильном смысле ряда задач теории расписаний. Техника доказательства результатов такого рода во многом напоминает приемы которые использовались при установлении NP трудности (в обычном смысле) экстремальных задач теории расписаний. Для доказательства NP-трудности в сильном смысле тон или иной экстремальной задачи будем доказывать №" трудность в сильном смысле соответствующей задачи распознавания. Для этого достаточно показать, что к ней сводится некоторая известная NP –полная в сильном смысле задача. В качестве такой задачи в данном параграфе выбрана задача о 3-разбиении, которая заключается в следующем. Имеется множество  каждому элементу которого поставлено в соответствие натуральное число (вес) е,, причем

Существует ли такое разбиение мужества.V⁰ на трехэлементные подмножества N°, N*..... N° такие, что  для всех;

Отметим, что условие  является существенным. Оно означает, что сумма весов любых четырех (и более) элементов будет больше, чем Е. а любых двух элементов - меньше, чем Е. Подчеркнем также то, что задача о разбиении - исторически первая задача, для которой установлена W-полнота в сильном смысле.

Чтобы обеспечить псевдополиномиальное сведение задачи с 3-раэбнении к некоторой задаче распознавания, необходимо преобразовать входную информацию задачи о 3-разбиении во входную информацию некоторой ее индивидуальной задачи распознавания. Число выполняемых при этом действий должно полиномиально зависеть от длины входа задачи о 3 разбиении, представленного в унарной системе счисления, другими словами, от величины  Иногда удается установить обычную полиномиальную сводимость. В этом случае число действий но преобразованию входной информации полиномиально зависит от  или даже от n₀. Построенная в результате преобразования входа задачи о З разбиении –индивидуальная задача распознавания должна иметь ответ тогда и только тогда, когда такой же ответ имеет задача о 3 разбиений.