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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
Ответ на этот вопрос был дан в работах Кобмена (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>DTIME</tex> и <tex>DSPACE</tex>, аналогичным образом определяются классы <tex>NSPACE</tex> и <tex>NTIME</tex> (префикс <tex>D</tex> соответствует детерминизму, а <tex>N</tex> — недетерминизму).
−
 
+
{{Определение
−
==Определение==
+
|definition=
−
Классом <tex>DTIME(f(n))</tex> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и время ее работы не превосходит <tex>f(n)</tex>, где <tex>n</tex> — длина входа. Формально, определение можно записать так:
+
<tex>DTIME(f(n)) = \{ L \mid \exists </tex> программа <tex>p : L(p)=L,</tex> для любого <tex>x</tex>, такого что <tex>|x| = n</tex>, где n — длина входа и <tex>Time(p,x) = O( f(n)) \}</tex>.
−
 
+
}}
−
<tex>DTIME(f(n)) = \{ L \mid \exists </tex> машина Тьюринга <tex>m : L(m)=L, Time(m,x) \le f(|x|) \}</tex>, где <tex>|x|</tex> &mdash; длина входа <tex>x</tex>.
+
{{Определение
−
 
+
|definition=
−
==Определение==
+
<tex>DSPACE(f(n)) = \{ L \mid \exists </tex> программа <tex>p : L(p)=L,</tex> для любого <tex>x</tex>, такого что <tex>|x| = n</tex>, где n — длина входа и <tex>Space(p,x) = O(f(n)) \}</tex>.
−
Классом <tex>DSPACE(f(n))</tex> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и память, используемая ею на любом входе, не больше <tex>f(n)</tex>, где <tex>n</tex> — длина входа. Формально, определение можно записать так:
+
}}
−
 
−
<tex>DSPACE(f(n)) = \{ L \mid \exists </tex> машина Тьюринга <tex>m : L(m)=L, Space(m,x) \le f(|x|) \}</tex>.
 
−
 
 
−
 
 
−
Аналогичным образом введем классы <tex>NSPACE</tex> и <tex>NTIME</tex>, использующие недетерминированную машину Тьюринга взамен детерминированной (префикс <tex>D</tex> соответствует детерминизму, а <tex>N</tex> — недетерминизму).
 
−
 
 
  
 
Через понятия классов <tex>DSPACE</tex>, <tex>DTIME</tex>, <tex>NSPACE</tex> и <tex>NTIME</tex> будет дано определение многим сложностным классам, в том числе классов [[Класс P|P]] и [[Недетерминированные вычисления. Классы NP и Σ₁|NP]].
 
Через понятия классов <tex>DSPACE</tex>, <tex>DTIME</tex>, <tex>NSPACE</tex> и <tex>NTIME</tex> будет дано определение многим сложностным классам, в том числе классов [[Класс P|P]] и [[Недетерминированные вычисления. Классы NP и Σ₁|NP]].
Строка 23: Строка 17:
 
== Вычисление с оракулом ==
 
== Вычисление с оракулом ==
 
Сложностный класс задач, решаемых алгоритмом из класса <tex>A</tex> с оракулом для языка <tex>B</tex> обозначают <tex>A^B</tex>. Так же <tex>A</tex> называют сложностным классом с доступом к оракулу <tex>B</tex>.
 
Сложностный класс задач, решаемых алгоритмом из класса <tex>A</tex> с оракулом для языка <tex>B</tex> обозначают <tex>A^B</tex>. Так же <tex>A</tex> называют сложностным классом с доступом к оракулу <tex>B</tex>.
−
Если <tex>B</tex> - это множество языков, то <tex>A^B =\bigcup_{D \in B}A^D</tex>, где <tex>D</tex> - язык из <tex>B</tex>.
+
Если <tex>B</tex> — это множество языков, то <tex>A^B =\bigcup\limits_{D \in B}A^D</tex>, где <tex>D</tex> — язык из <tex>B</tex>.

Версия 20:30, 7 мая 2012

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

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

Для начала введем понятия [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]x[/math], такого что [math]|x| = n[/math], где n — длина входа и [math]Time(p,x) = O( f(n)) \}[/math].


Определение:
[math]DSPACE(f(n)) = \{ L \mid \exists [/math] программа [math]p : L(p)=L,[/math] для любого [math]x[/math], такого что [math]|x| = n[/math], где n — длина входа и [math]Space(p,x) = O(f(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\limits_{D \in B}A^D[/math], где [math]D[/math] — язык из [math]B[/math].

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Сложностные_классы._Вычисления_с_оракулом&oldid=21991»