10.4.Некоторые результаты

Обозначим через SPACE(f(n)) класс задач (языков), для которых существует МТ, работающая на памяти с объемом, ограниченным f(n).

Аналогично NSPACE(f(n)) класс задач (языков), для которых существует НМТ, работающая на памяти с объемом, ограниченным f(n).

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

Теорема 9.7. NSPACE(f(n))SPACE(f(n)²).

11.Подходы к решению np-полных задач

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

1. Анализируется структура NPC. Оказывается, что в этом классе можно выделить «более легкие» и «более сложные» задачи. И уже в зависимости от того, какой является ваша задача Z, вы можете подбирать методы решения.

2. Для задач в оптимизационной форме требования к точности можно ослабить, т.е. вместо оптимального искать приближенное решение.

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

4. Задачу всегда можно решить полным перебором. В некоторых случаях комбинаторная структура задачи позволяет разработать достаточно сложные и тонкие алгоритмы «направленного перебора», которые теоретически будут экспоненциальными, но на практике могут успешно использоваться.

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

11.1.NP-полнота в сильном смысле. Псевдополиномиальные алгоритмы

Пусть I – некоторая индивидуальная задача массовой задачи Z. Отметим, что задавая условие задачи (слово I в некотором алфавите) мы должны задать «комбинаторные» параметры задачи - число вершин, число ребер, число переменных, число дизъюнкций, ребра графа и т.п. – и «числовые» параметры: веса ребер графа, вектора объемов и стоимостей в задаче о рюкзаке, веса камней в задаче о камнях и т.п. Обозначим через num(I) – максимальное число, которое используется при задании I.

Разумная кодировка предполагает, что для записи num(I) потребуется слово длины log(num(I)). Поэтому в P лежат задачи, для которых существуют алгоритмы решения с трудоемкостью, полиномиальной по |I| и log(num(I)).

Опр. Алгоритм решения задачи называется псевдополиномиальным, если он решает задачу за время, ограниченное полиномом от |I| и num(I).

Для большинства задач из NPC нет не только полиномиальных, но и псевдополиномиальных алгоритмов, поэтому наличие для задачи из NPC псевдополиномиального алгоритма, что она в каком-то смысле «проще», чем задача, для которой нет псевдополиномиального алгорима.

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

Рассмотрим теперь задачи, для которых пока нет псевдополиномиального алгоритма. Для некоторых из них доказано, что они являются NP-полными даже тогда, когда num(I)≤p(|I|), где p(|I|)– полином от |I|. Такие задачи называются NP –полными в сильном смысле (сильно NP-полными).

Таким образом, класс NPC разбивается на три части: задачи с известными псевдополиномиальными алгоритмами; задачи, для которых не построены псевдополиномиальные алгоритмы, но и не доказано, что они сильно NP-полные; сильно NP-полные задачи. Если вам придется иметь дело с последними, то, по-видимому, ничего не остается как использовать либо эвристические алгоритмы, либо методы направленного перебора (см. ниже).