Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Полиномиальная и недетерминированная полиномиальная временная сложность
Множество задач, которые могут быть решены за полиномиально-ограниченное время на детерминированных машинах, обозначим через Р:
Р == È DTIME (n^) [^=i].
I ³ l
Задачи из Р называют эффективно решаемыми.
Ряд важных задач могут быть достаточно просто решены на недетерминированных полиномиально-ограниченных по времени Т-машинах. Класс этих задач обозначим через NP:
NP = È NTIME (n^).
i ³1
Пример (задача из NP). Следующая задача входит в класс NP. Для заданного графа с k вершинами определить, имеется ли циклически замкнутая трасса, на которой лежат все вершины графа. Такая трасса называется направленным обходом Гамильтона.
Конечно, можно и для ленточной сложности ввести аналогичные образования классов задач. Определим
pspace = È DSPACE(n^),
i³l
