Полная версия

Главная arrow Логистика arrow Методы управления инвестициями в логистических системах

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Взаимоотношения между классами NP и Р

Вопрос о взаимоотношении классов NP и Р имеет важное значение для теории NP-полных задач. Одно соотношение заключается в том, что

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

Если II е Р и А — произвольный детерминированный алгоритм решения задачи II, то полиномиальный недетерминированный алгоритм для II можно получить, воспользовавшись А в качестве стадии проверки и игнорируя стадию угадывания. Таким образом, из II е Р следует, что II е NP.

Один из самых значительных результатов относительно соотношения классов Р и NP состоит в следующем.

Теорема 9.1. Если II е NP, то существует такой полином Р, что задача II может быть решена детерминированным алгоритмом с временной сложностью 0(2Р(/7)).

Доказательство. Пусть А — полиномиальный недетерминированный алгоритм решения задачи II и q(n) — полином, ограничивающий временную сложность алгоритма А.

По определению класса NP для каждого принимаемого входа длиной п найдется некоторое слово-догадка (в алфавите Г символов ленты) длиной не более q(n), такое, что в алгоритме А стадия проверки дает при рассматриваемом входе ответ «да» не более чем за q(n) шагов. Таким образом, общее число догадок, которые нужно рассмотреть, не превосходит Kq(n где К= |Г| (если слово-догадка короче q(n), то его можно дополнить пустыми словами и рассматривать как слово длиной q(n)).

Теперь можно детерминированным образом выяснить, имеет ли алгоритм А на заданном входе длиной п принимающее вычисление. Для этого достаточно на каждой из Kq(n) возможных догадок запустить детерминированную стадию проверки алгоритма А и позволить ей работать до того момента, пока она не остановится или не сделает q(n) шагов. Этот моделирующий алгоритм даст ответ «да», если ему встретится слово-догадка, приводящее к принимающему вычислению, не более q(n), и ответ «нет» — в противном случае. Такой алгоритм, очевидно, будет детерминированным алгоритмом решения задачи II. Более того, его временная сложность равна по существу q{n)Kq(n) и, хотя это экспонента, при подходящем выборе полинома сложность не превосходит 0(2Р(/!)). Теорема доказана.

Процесс моделирования, предложенный в доказательстве теоремы 9.1, можно в некоторой степени ускорить с помощью метода ветвей и границ или путем более тщательного перебора, когда избегаются ненужные слова-догадки. Тем не менее, несмотря на значительное сокращение перебора в этом случае, неизвестен метод, который осуществляет такое моделирование быстрее, чем за экспоненциальное время.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>