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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (недетерминированная машина тьюринга -> НМТ)
м (добавлены разделы см. также и источники)
Строка 40: Строка 40:
 
<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>).
 
<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>).
 
}}
 
}}
 +
 +
== См. также ==
 +
== Литература и источники информации ==
 +
  
 
[[Категория: Теория сложности]]
 
[[Категория: Теория сложности]]

Версия 01:10, 10 марта 2016

Определения

В основных понятиях теории сложности используются такие величины, как время работы и объем затрачиваемой памяти.

Определение:
[math]\mathrm{T}(m,x)[/math] — время работы машины Тьюринга [math]m[/math] на входе [math]x[/math].


Определение:
[math]\mathrm{S}(m,x)[/math] — объем памяти, требуемый машине Тьюринга [math]m[/math], для выполнения на входе [math]x[/math].


Для того, чтобы дать определения многим сложностным классам, понадобится определить такие классы, как [math]\mathrm{DTIME}[/math] и [math]\mathrm{DSPACE}[/math] (префикс [math]\mathrm{D}[/math] соответствует детерминизму).

Определение:
[math]\mathrm{DTIME}(f(n))[/math] --- класс языков [math]L[/math], для которых существует детеминированная машина Тьюринга [math]m[/math] такая, что [math]L(m) = L[/math] и для любого [math]x[/math] из [math]L[/math] выполнено [math]\mathrm{T}(m,x) \le f(n)[/math] (здесь [math]n[/math] — длина [math]x[/math]).


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


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


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

Определение:
Недетерминированная машина Тьюринга (НМТ) — машина Тьюринга, управляющее устройство которой представляет собой недетерминированный конечный автомат, то есть из каждого состояния может быть несколько переходов по одному и тому же символу на входной ленте.


Определение:
[math]\mathrm{NTIME}(f(n))[/math] — класс языков [math]L[/math], для которых существует НМТ [math]m[/math] такая, что [math]L(m)=L[/math] и для любого [math]x[/math] из [math]L[/math] выполнено [math]\mathrm{T}(m,x) = O(f(n))[/math] (здесь [math]n[/math] — длина [math]x[/math]).


Определение:
[math]\mathrm{NSPACE}(f(n))[/math] — класс языков [math]L[/math], для которых существует НМТ [math]m[/math] такая, что [math]L(m)=L[/math] и для любого [math]x[/math] из [math]L[/math] выполнено [math]\mathrm{S}(m,x) = O(f(n))[/math] (здесь [math]n[/math] — длина [math]x[/math]).


См. также

Литература и источники информации