Изменения

<tex>\mathrm{T}(pm,x)</tex> — время работы программы [[Машина_Тьюринга | машины Тьюринга]] <tex>pm</tex> на входе <tex>x</tex>.

<tex>\mathrm{S}(pm,x)</tex> — объем памяти, требуемый программе машине Тьюринга <tex>pm</tex> , для выполнения на входе <tex>x</tex>.

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

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

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

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