Сложностные классы

История

В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на её размерность. Какие задачи могут быть решены на ЭВМ за реальное время? Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы P, NP и т.д.

Определения

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.

Определение:

[math]\mathrm{T}(p,x)[/math] — время работы программы р на входе х.

Определение:

[math]\mathrm{S}(p,x)[/math] — объем памяти, требуемый программе р для выполнения на входе х.

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как [math]\mathrm{DTIME}[/math] и [math]\mathrm{DSPACE}[/math] (префикс [math]\mathrm{D}[/math] соответствует детерминизму).

Определение:

[math]\mathrm{DTIME}(f(n))[/math] — класс языков [math]L[/math], для которых существует детерминированная программа [math]p[/math] такая, что [math]L(p)=L[/math] и для любого [math]x[/math] из [math]L[/math] выполнено [math]\mathrm{T}(p,x) = O(f(n))[/math] (здесь [math]n[/math] — длина [math]x[/math]). [math]\mathrm{DSPACE}(f(n))[/math] — класс языков [math]L[/math], для которых существует детерминированная программа [math]p[/math] такая, что [math]L(p)=L[/math] и для любого [math]x[/math] из [math]L[/math] выполнено [math]\mathrm{S}(p,x) = O(f(n))[/math] (здесь [math]n[/math] — длина [math]x[/math]).

Определение:

[math]\mathrm{TS}(f,g)[/math] — класс языков [math]L[/math], для которых существует детерминированная программа [math]p[/math] такая, что [math]L(p)=L[/math] и для любого [math]x[/math] из [math]L[/math] выполнено [math]\mathrm{T}(p,x) = O(f(n))[/math] и [math]\mathrm{S}(p,x) = O(g(n))[/math], где [math]x[/math] — длина входа.

Аналогичным образом определяются классы [math]\mathrm{NSPACE}[/math] и [math]\mathrm{NTIME}[/math] (префикс [math]\mathrm{N}[/math] соответствует недетерминизму).

Определение:

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

Определение:

[math]\mathrm{NTIME}(f(n))[/math] — класс языков [math]L[/math], для которых существует недетерминированная программа [math]p[/math] такая, что [math]L(p)=L[/math] и для любого [math]x[/math] из [math]L[/math] выполнено [math]\mathrm{T}(p,x) = O(f(n))[/math] (здесь [math]n[/math] — длина [math]x[/math]). [math]\mathrm{NSPACE}(f(n))[/math] — класс языков [math]L[/math], для которых существует недетерминированная программа [math]p[/math] такая, что [math]L(p)=L[/math] и для любого [math]x[/math] из [math]L[/math] выполнено [math]\mathrm{S}(p,x) = O(f(n))[/math] (здесь [math]n[/math] — длина [math]x[/math]).