5.4. Труднорешаемые задачи

NP-полная задача П называется универсальной, если к ней полиномиально сводится любая NP-полная задача. Выше была доказана принадлежность задачи выполнимости к.н.ф. к классу NPполных задач.

Приведем другие примеры задач этого класса: о полном подграфе, о вершинном покрытии, о сложности д.н.ф. частичной булевой функции и о трехмерном сочетании.

Задача о полном подграфе. Граф называется полным, если

любые две его вершины соединены ребром. По заданному неориентированному графу G и числу k требуется определить, имеется ли в G полный подграф с k вершинами.

Задача о вершинном покрытии. Некоторое подмножество V′,

содержащее k= V′ вершин, образует вершинное покрытие мощности k графа G, если для любого ребра найдется инцидентная ему вершина в подмножестве V′.

По заданному графу G и числу k требуется определить, имеет ли G вершинное покрытие мощности k.

Задача о сложности д.н.ф. частичной булевой функции. По частичной булевой функции f и числу k необходимо установить, возможно ли построить д.н.ф. для f, содержащую не более k букв.

Трехмерное сочетание. Дано множество M W×X×Y, где W,X,Y

– непересекающиеся множества, содержащие одинаковое число элементов q. Необходимо установить, что M содержит трехмерное сочетание, т.е. подмножество M′ M такое, что M′ =q и никакие два разных элемента M′не имеют ни одной равной координаты.

Например, W={a,b,c}, X={d,e,f}, Y={j,h,i} и M = {(a,d,i), (a,e,i), (a,f,j), (b,e,i), (b,f,j), (c,e,h), (c,d,i)}. Данный пример имеет положительное решение: M′={(a,d,i), (b,f,j), (c,e,h)} M.

Пусть П1 – задача о выполнимости к.н.ф. Тогда, чтобы доказать,

179

что задача Пq является NP-полной, достаточно доказать, что П1 П2 … Пq.

Например, в [15] показано, что задача выполнимости к.н.ф сводится к задаче о полном подграфе, которая в свою очередь сводится к задаче о вершинном покрытии, а последняя - к задаче о сложности д.н.ф. частичной булевой функции.

NP-трудные задачи

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

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

Приведем примеры NP-трудных задач: задача коммивояжера и задача построения сингулярной скобочной формы.

Задача коммивояжера. Эта задача, поставленная еще в 1934 г., является одной из самых важнейших задач в теории графов. В области оптимизации дискретных задач задача коммивояжера служит своеобразным полигоном, на котором испытываются все новые методы.

Постановка задачи. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2, 3, …, n и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим? В терминах теории графов: найти гамильтонов цикл в графе минимальной длины.

Задача построения сингулярной скобочной нормальной

180