42
правки
Изменения
1.1.1.2 поправлен tex на переменных (пока не на всех, во втором определении при оборачивании x в tex все ломается)
{{Определение
|definition=
<tex>\mathrm{T}(p,x)</tex> — время работы программы р <tex>p</tex> на входе х<tex>x</tex>.
}}
{{Определение
|definition=
<tex>\mathrm{S}(p,x)</tex> — объем памяти, требуемый программе р <tex>p</tex> для выполнения на входе хx.
}}
{{Определение
|definition=
<tex>\mathrm{DTIME}(f(n))</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>n</tex> — длина <tex>x</tex>).<br>
}}
{{Определение
|definition=
{{Определение
|definition=
<tex>\mathrm{NTIME}(f(n))</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>n</tex> — длина <tex>x</tex>).<br>
}}
{{Определение
