На этом шаге мы рассмотрим теорему о принадлежности задачи ВЫПОЛНИМОСТЬ к классу сложности NP.

Теорема.

Задача ВЫПОЛНИМОСТЬ принадлежит классу NP.

Доказательство.

Оно проводится конструктивно, путем построения алгоритма для недетерминированной машины:

  for i:= 1 to n do 
      x:= выбор({0, 1}); 
   if Φ(x1, x2, ..., xn) then успех
   else неудача

    Этот алгоритм работает следующим образом. Многозначная функция выбор создает при первом выполнении тела цикла сразу два экземпляра переменной x₁ одно со значением 0, другое со значением 1. Для каждого экземпляра (варианта) создается процесс - копия следующего (условного) оператора. Эти копии можно записать так:

  if Φ(0, x2, ..., xn) then успех
  else неудача, 

  if Φ(1, x2, ..., xn) then успех
  else неудача

    При втором выполнении тела цикла создаются два экземпляра переменной х₂ со значениями 1 и 0. Для каждого экземпляра создается процесс - копия существующих процессов. В результате будет создано уже четыре процесса:

  if Φ(0, 0, ..., xn) then успех
  else неудача, 

  if Φ(1, 0, ..., xn) then успех
  else неудача, 

  if Φ(0, 1, ..., xn) then успех
  else неудача, 

  if Φ(1, 1, ..., xn) then успех
  else неудача

    По окончании оператора цикла возникнет 2ⁿ процессов, каждый из которых будет назначен на свой процессор недетерминированной машины. Вычисления значений Φ(a₁, a₂, ..., a_n) будут происходить параллельно и закончатся за ограниченное относительно длины формулы время. Процессы, которые вырабатывают значение неудача, сразу завершаются без последствий для других процессов. Процесс, который первым выработал значение успех, выдает его в качестве общего результата работы всей недетерминированной программы, затем завершается сам и завершает остальные процессы. Таким образом, выполнима или не выполнима формула (выражение) узнаем за полиномиальное время работы недетерминированной машины. Доказательство завершено.

    Небольшой комментарий.

    В тексте:

  for j := 1 to n do 
    хi := выбор({0, 1}); 
  if Φ(x1, x2, ..., xn) then успех 
  else неудача

оператор цикла строит упоминавшееся выше дерево возможностей - возможностей присваивания переменным x значений. Это дерево в итоге будет выглядеть, как показано на рисунке 1.

Рис.1. Процесс вычисления значения булевой функции на недетерминированной машине

    Требуется создать 2ⁿ процессов для параллельного прохождения по всем ветвям.

    Если же мы изменим текст недетерминированной программы так:

  Угадать набор (x1, x2, ..., xn); 
  if Φ(x1, x2, ..., xn)  then успех
  else неудача,

то получим тот же результат за то же время, но при прохождении по одной ветви. Дерево в этом случае не строится, а ветвь угадывается.

    На следующем шаге мы рассмотрим связь между классами P и NP.

Предыдущий шаг Содержание Следующий шаг