Теорема 1.

Того что вы утверждаете не обнаружено. К тому же я повторил формулировку.
Теорема 1.
mihaild в сообщении #1367982
писал(а):
Пусть

- язык из

,

- распознающая его МТ. Определим функцию

, ограниченную полиномом, такую что для любого слова

оно принадлежит языку тогда и только тогда, когда существует подсказка длины не больше чем
... . Тогда длина данной подсказки возрастает не более ,чем полином

,где

- параметр ,который равен радиусу шара с центром в

. То есть :

Для какого

?
Для которого условие .
Пусть она работает следующим образом : сначала проходит все точки шара радиуса 1 ,попутно проверяя не являются ли они подсказкой , если среди них нет искомого ,переходит к точкам шара радиуса 2 также подставляя значения ,и так далее ,пока полученное значение не окажется подсказкой.
Теорема 1 про что-то невнятное.
Чуть выше требуемая формулировка.