Конспект установочных лекций по комплексному курсу Информатика, Теория информации

Полиномиальная и недетерминированная полиномиальная временная сложность


Множество задач, которые могут быть решены за полиномиально-ограниченное время на детерминированных машинах, обозначим через Р:   

Р == È DTIME (n^)           [^=i].

I ³ l

Задачи из Р называют эффективно решаемыми.

Ряд важных задач могут быть достаточно просто решены на недетерминированных полиномиально-ограниченных по времени Т-машинах. Класс этих задач обозначим через NP:

NP = È NTIME (n^).

        i ³1         

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

Конечно, можно и для ленточной сложности ввести аналогичные образования классов задач. Определим

pspace = È DSPACE(n^),

               i³l



Содержание раздела