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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Вычисление с оракулом)
Строка 27: Строка 27:
 
Оракул — программа <tex>A(x)</tex>, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x \in A</tex>.
 
Оракул — программа <tex>A(x)</tex>, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x \in A</tex>.
 
}}
 
}}
Сложностный класс задач, решаемых алгоритмом из класса <tex>C</tex> с оракулом для языка <tex>A</tex>, обозначают <tex>C^A</tex>.  
+
Сложностный класс задач, решаемых алгоритмом из класса <tex>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.  
Если <tex>A</tex> — множество языков, то <tex>C^A =\bigcup\limits_{D \in A}C^D</tex>.
+
Если <tex>\mathrm{A}</tex> — множество языков, то <tex>\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}</tex>.
  
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]

Версия 01:31, 2 июня 2012

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

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

Определение:
[math]\mathrm{T(p,x)}[/math] — ограничение по времени.

[math]\mathrm{S(p,x)}[/math] — ограничение по памяти.

[math]\mathrm{TS(p,x)}[/math] — ограничение и по времени и по памяти.


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


Определение:
[math]\mathrm{DTIME(f(n))} = \{ L \mid \exists [/math] программа [math]p : L(p)=L[/math] и для [math]\forall x[/math], такого что [math]|x| = n[/math] (здесь [math]n[/math] — длина входа), [math]\mathrm{T(p,x)} = O(f(n)) \}[/math].


Определение:
[math]\mathrm{DSPACE(f(n))} = \{ L \mid \exists [/math] программа [math]p : L(p)=L[/math] и для [math]\forall x[/math], такого что [math]|x| = n[/math] (здесь [math]n[/math] — длина входа), [math]\mathrm{S(p,x)} = O(f(n)) \}[/math].


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

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

Определение:
Оракул — программа [math]A(x)[/math], вычисляющая за [math]O(1)[/math] времени, верно ли, что [math]x \in A[/math].

Сложностный класс задач, решаемых алгоритмом из класса [math]\mathrm{C}[/math] с оракулом для языка [math]\mathrm{A}[/math], обозначают [math]\mathrm{C^A}[/math]. Если [math]\mathrm{A}[/math] — множество языков, то [math]\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}[/math].