Сложностные классы. Вычисления с оракулом

В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время?

Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964), и Эдмнодса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы P, NP и т.д.

Для начала введем понятия [math]DTIME[/math] и [math]DSPACE[/math].

Определение

Классом [math]DTIME(f(n))[/math] называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и время ее работы не превосходит [math]f(n)[/math], где [math]n[/math] — длина входа. Формально, определение можно записать так:

[math]DTIME(f(n)) = \{ L \mid \exists [/math] машина Тьюринга [math]m : L(m)=L, Time(m,x) \le f(|x|) \}[/math], где [math]|x|[/math] — длина входа [math]x[/math].

Определение

Классом [math]DSPACE(f(n))[/math] называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше [math]f(n)[/math], где [math]n[/math] — длина входа. Формально, определение можно записать так:

[math]DSPACE(f(n)) = \{ L \mid \exists [/math] машина Тьюринга [math]m : L(m)=L, Space(m,x) \le f(|x|) \}[/math].

Аналогичным образом введем классы [math]NSPACE[/math] и [math]NTIME[/math], использующие недетерминированную машину Тьюринга взамен детерминированной (префикс [math]D[/math] соответствует детерминизму, а [math]N[/math] — недетерминизму).

Через понятия классов [math]DSPACE[/math], [math]DTIME[/math], [math]NSPACE[/math] и [math]NTIME[/math] будет дано определение многим сложностным классам, в том числе классов P и NP.

Вычисление с оракулом

Сложностный класс задач, решаемых алгоритмом из класса [math]A[/math] с оракулом для языка [math]B[/math] обозначают [math]A^B[/math]. Так же [math]A[/math] называют сложностным классом с доступом к оракулу [math]B[/math]. Если [math]B[/math] - это множество языков, то [math]A^B =\bigcup_{D \in B}A^D[/math], где [math]D[/math] - язык из [math]B[/math].