Бюрократы, editor, Администраторы
422
правки
Изменения
→Странное ограничение
Я правильно понимаю, что на <tex>i</tex>-ом шаге <tex>n</tex> не зависит от <tex>M_i</tex>? Тогда я не понимаю: что плохого в том, что машина <tex>M_i</tex> не разрешает слово <tex>1^n</tex> за <tex>2^{n - 1}</tex> шагов, потому как временной полином для этой машины вполне может выглядеть как:
<tex>p(k) = 2^n k </tex>.<br/>
(Друзья, давайте, всё-таки, будем подписываться! Или, хотя бы, логиниться. -- [[Участник:Kirelagin|Кирилл Елагин]] 23:06, 3 июня 2012 (GST))
Я понимаю, что такое время работы программы на данном входе. Я не понимаю, что такое «программа (не) разрешает такой-то язык за время <tex>p(k) = 2^{n k -1}</tex>».[[Участник:Kirelagin|Кирилл Елагин]] 23:06, 3 июня 2012 (GST)
