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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
  
 
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Недетерминированные вычисления. Классы NP и Σ₁|NP]] и т.д.
 
Ответ на этот вопрос был дан в работах Кобхэма (Alan Cobham, 1964) и Эдмондса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Недетерминированные вычисления. Классы NP и Σ₁|NP]] и т.д.
 
Для начала введём понятия <tex>DTIME</tex> и <tex>DSPACE</tex>, аналогичным образом определяются классы <tex>NSPACE</tex> и <tex>NTIME</tex> (префикс <tex>D</tex> соответствует детерминизму, а <tex>N</tex> — недетерминизму).
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 10: Строка 8:
 
<tex>TS(p,x)</tex> — ограничение и по времени и по памяти.
 
<tex>TS(p,x)</tex> — ограничение и по времени и по памяти.
 
}}
 
}}
 +
 +
Введём понятия <tex>DTIME</tex> и <tex>DSPACE</tex>, аналогичным образом определяются классы <tex>NSPACE</tex> и <tex>NTIME</tex> (префикс <tex>D</tex> соответствует детерминизму, а <tex>N</tex> — недетерминизму).
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=

Версия 17:54, 1 июня 2012

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

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

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

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

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


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


Определение:
[math]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]T(p,x) = O(f(n)) \}[/math].


Определение:
[math]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]S(p,x) = O(f(n)) \}[/math].


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

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

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

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