Изменения
another vague statement
У меня вопрос. Разве следующее утверждение верное: «Так как <tex>L \in \mathrm{PS}</tex>, то существует какая-то детерминированная машина Тьюринга <tex>M</tex>, которая его распознаёт за полиномиальное от размера входа время.»? --[[Участник:Байдаров Андрей|Байдаров Андрей]] 01:46, 2 июня 2012 (GST)
:Думаю, что нет. И как мне кажется, единственное, где здесь должно присутствовать полиномиальное время, {{---}} это <tex>f</tex>, но к сожалению я не смог найти: почему время выполнения <tex>f</tex> полиномиальное.
