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

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

Перечисленные выше задачи не исчерпывают всего многообразия задач, принадлежащих классу P. Класс задач, не решаемых за полиномиальное время, намного шире. Среди них выделяют класс Eзадач, экспоненциальных по природе, и класс NP–недетерминированныхполиномиальныхзадач.

Экспоненциальнойпоприроде считается задача, сложность которой не менее порядка O(fⁿ), где f - константа или полином от n. К классу Eотносятся, например, задачи, в которых требуется построить все подмножества некоторого множества, задачи распознавания правильных выражений на некоторых формальных языках, большинство задач теории автоматов и другие.

При небольших значениях n экспоненциальный алгоритм может быть более быстрым, чем полиномиальный. Однако различие между классами задач Eи Pвелико и всегда проявляется при больших значениях n.

На практике встречаются задачи, не попадающие ни в класс P, ни в классE. В условиях этих задач не содержится экспоненциальных вычислений, но для многих из них до сих пор не разработан полиномиальный алгоритм.

Примеры таких задач

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

В настоящее время ни для одной из 9 перечисленных выше задач не найдено полиномиального алгоритма. Более того, для этих задач была доказана попарная эквивалентность, то есть если удастся представить для одной из этих задач полиномиальный алгоритм, то все они будут автоматически решены.

Все задачи, не попадающие ни в класс P, ни в класс E, являются трудными и по определению относятся к области искусственного интеллекта.

Для полноты изложения определим еще классNPнедетерминированных полиномиальных задач. Предварительно опишем два семейства абстрактных моделей полиномиального алгоритма.

Абстрактной моделью такого полиномиального алгоритма является «черный ящик» (автомат), умеющий выполнять только заданное множество элементарных операций, например: +,-, *,/, Ú(или), & (и),читать, печать, если... то..., повторять.

В заданный момент времени автомат находится в строго определенном состоянии.

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

Механизм перебора, совершая предварительные попытки, можно смоделировать с помощью другой, тоже весьма абстрактной машины Тьюринга, называемой недетерминированной.

Всякий алгоритм, который может быть выполнен за полиномиальное время на недетерминированной машине Тьюринга, называется недетерминированнымполиномиальнымалгоритмом или алгоритмом, принадлежащим классу NP.

Ясно, что PÌNP, поскольку детерминированная машина Тьюринга является частным случаем недетерминированной. В настоящее время нет ответа на вопрос P=NPили нет.

Из списка задач 1-9, не попадающих ни в класс P, ни в классE, к классу NPотносятся задачи 1,3,4 и 7.

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

12 Следующая ⇒