5.4 Иерархия по сложности. Труднорешаемые задачи.

Рассмотрим следующие классы задач:

• P (P-time) – класс задач, решаемых за полиномиальное время на ДМТ.

• NP (NP-time) – класс задач, решаемых за полиномиальное время на НДМТ.

• P-space – класс задач, которые решаются на обычной машине Тьюринга с использованием не более, чем полиномиальной памяти.

• NP-space – класс задач, которые могут быть решены на НДМТ с полиномиальной памятью.

Теорема 5.8 P-time  P-space

NP-time  NP-space

Доказательство. Ясно, что, работая полиномиальное время, мы используем не более, чем полиномиальную память.

Теорема 5.9 P-space=NP-space

Доказательство. Что P-space  NP-space очевидно, так как детерминированная машина всегда может рассматриваться как недетерминированная.

Докажем обратное вхождение .

Пусть Т – некоторая задача, которую мы умеем решать на НДМТ М с использованием полиномиальной памяти. Научимся ее решать также с использованием не более, чем полиномиальной памяти на обычной машине Тьюринга М₁.

Наша М₁ перебирает все возможные варианты в работе исходной НДМТ М и после окончания разбора очередного варианта освобождает память. Поэтому нам потребуется столько же памяти, сколько требуется для работы исходной машины М, но при этом надо вводить дополнительную память для кодирования номера рассматриваемого варианта. Для этого потребуется не более, чем P(n) ячеек(при двоичной кодировке).

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

Теорема доказана.