Изменения
Новая страница: «В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для...»
В начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время?
Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964), и Эдмнодса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Недетерминированные вычисления. Классы NP и Σ₁|NP]] и т.д.
Для начала введем понятия <tex>DTIME</tex> и <tex>DSPACE</tex>.
==Определение==
Классом <tex>DTIME(f(n))</tex> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и время ее работы не превосходит <tex>f(n)</tex>, где <tex>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> — длина входа <tex>x</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>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>.
==Ссылки==
СТАНОЧЕГ ;)
Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964), и Эдмнодса (Jack Edmonds, 1965), где были введены сложностные классы задач. К ним относятся классы [[Класс P|P]], [[Недетерминированные вычисления. Классы NP и Σ₁|NP]] и т.д.
Для начала введем понятия <tex>DTIME</tex> и <tex>DSPACE</tex>.
==Определение==
Классом <tex>DTIME(f(n))</tex> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и время ее работы не превосходит <tex>f(n)</tex>, где <tex>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> — длина входа <tex>x</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>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>.
==Ссылки==
СТАНОЧЕГ ;)
