Изменения

Для начала введем понятия <tex>DTIME</tex> и <tex>DSPACE</tex>. ==Определение==Классом , аналогичным образом определяются классы <tex>DTIME(f(n))NSPACE</tex> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, и время ее работы не превосходит <tex>fNTIME</tex> (n)префикс <tex>D</tex>соответствует детерминизму, где а <tex>nN</tex> — длина входанедетерминизму). Формально, определение можно записать так: {{Определение|definition=<tex>DTIME(f(n)) = \{ L \mid \exists </tex> машина Тьюринга программа <tex>m p : L(mp)=L, Time(m,x) \le f(|x|) \}</tex>, где для любого <tex>|x|</tex> &mdash; длина входа , такого что <tex>|x</tex>. ==Определение=| =Классом <tex>DSPACE(f(n))</tex> называется множество языков, для которых существует машина Тьюринга такая, что она всегда останавливается, где n — длина входа и память, используемая ею на любом входе, не больше <tex>Time(p,x) = O( f(n)) \}</tex>, где <tex>n</tex> — длина входа. Формально, определение можно записать так: }}{{Определение|definition=<tex>DSPACE(f(n)) = \{ L \mid \exists </tex> машина Тьюринга программа <tex>m p : L(mp)=L, Space(m,x) \le f(|x|) \}</tex>.  Аналогичным образом введем классы для любого <tex>NSPACEx</tex> и , такого что <tex>NTIME|x| = n</tex>, использующие недетерминированную машину Тьюринга взамен детерминированной (префикс где n — длина входа и <tex>D</tex> соответствует детерминизмуSpace(p, а <tex>Nx) = O(f(n)) \}</tex> — недетерминизму).}}

Если <tex>B</tex> - — это множество языков, то <tex>A^B =\bigcup_bigcup\limits_{D \in B}A^D</tex>, где <tex>D</tex> - — язык из <tex>B</tex>.