Изменения

Перейти к: навигация, поиск

Теорема Бейкера — Гилла — Соловэя

1 байт убрано, 19:36, 5 июня 2013
Теорема
В начале каждой итерации определимся с тем, с какой длиной слова <tex>n</tex> мы будем работать. Для <tex>n</tex> должны быть выполнены два условия:
* <tex>2^n > T(M_i, (1)^1</tex> (это ограничение может быть достигнуто, так как мы исследуем только полиномиальные программы)
* <tex>n > \max_{s \in B} |s|}</tex> (это ограничение может быть достигнуто, так как в множестве <tex>B</tex> всегда конечное количество элементов)
Анонимный участник

Навигация