Изменения
→Определение
{{Определение
|definition=
'''Класс''' <tex>\mathrm{P}</tex> {{---}} класс языков (задач), разрешимых на детерминированной машине Тьюринга за полиномиальное время, то есть:<tex>\mathrm{P } = \bigcup\limits_{p \in poly}DTIME(p(n))</tex><ref>[[Сложностные классы. Вычисления с оракулом]]</ref>.
}}
Итого, язык <tex>L</tex> лежит в классе <tex>\mathrm{P}</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных;
# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;
