Просмотр исходного текста страницы Сложностные классы

== Определения ==

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.
{{Определение
|definition=
<tex>\mathrm{T}(m,x)</tex> — время работы [[Машина_Тьюринга | машины Тьюринга]] <tex>m</tex> на входе <tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(m,x)</tex> — объем памяти, требуемый машине Тьюринга <tex>m</tex>, для выполнения на входе <tex>x</tex>.
}}

Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как <tex>\mathrm{DTIME}</tex> и <tex>\mathrm{DSPACE}</tex>  (префикс <tex>\mathrm{D}</tex> соответствует детерминизму).
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</tex> --- класс языков <tex>L</tex>, для которых существует детеминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m) = L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) \le f(n)</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{DSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует детерминированная машина Тьюринга <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

{{Определение
|definition=
<tex>\mathrm{TS}(f,g)</tex> — класс языков <tex>L</tex>, для которых существует детерминированная программа <tex>p</tex> такая, что <tex>L(p)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(p,x) = O(f(n))</tex> и <tex>\mathrm{S}(p,x) = O(g(n))</tex>, где <tex>x</tex> — длина входа.
}}

Аналогичным образом определяются классы <tex>\mathrm{NSPACE}</tex> и <tex>\mathrm{NTIME}</tex>  (префикс <tex>\mathrm{N}</tex> соответствует недетерминизму).
{{Определение
|definition=
'''Недетерминированная машина Тьюринга''' (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой [[Недетерминированные_конечные_автоматы | недетерминированный конечный автомат]], то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.
}}
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{T}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}
{{Определение
|definition=
<tex>\mathrm{NSPACE}(f(n))</tex> — класс языков <tex>L</tex>, для которых существует НМТ <tex>m</tex> такая, что <tex>L(m)=L</tex> и для любого <tex>x</tex> из <tex>L</tex> выполнено <tex>\mathrm{S}(m,x) = O(f(n))</tex> (здесь <tex>n</tex> — длина <tex>x</tex>).
}}

== См. также ==
== Литература и источники информации ==


[[Категория: Теория сложности]]