141
правка
Изменения
м
→Определение: "В перечислениях в конце каждого пункта ставится либо точка, либо точка с запятой"
Итого, язык <tex>L</tex> лежит в классе <tex>P</tex> тогда и только тогда, когда существует такая детерминированная машина Тьюринга <tex>m</tex>, что:
# <tex>m</tex> завершает свою работу за полиномиальное время на любых входных данных ;# если на вход машине <tex>m</tex> подать слово <tex>l \in L</tex>, то она допустит его;# если на вход машине <tex>m</tex> подать слово <tex>l \not\in L</tex>, то она не допустит его.
== Свойства класса P ==
