Изменения

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

Теорема Ладнера

52 байта добавлено, 16:13, 3 июня 2012
м
Нет описания правки
* Если <tex>(\log_2 n)^{g(n)} \ge n</tex>, то <tex>g(n+1) := g(n)</tex>. Иначе выполняем один из следующих пунктов.
* Пусть вычисленное значение <tex>g(n)</tex> чётно. Определим <tex>g(n+1)</tex> такследущим образом:
for <tex>x</tex> : <tex>|x| \le \log_2 n</tex>
<tex>g(n+1) := g(n)</tex>
* Пусть вычисленное значение <tex>g(n)</tex> нечётно. Определим <tex>g(n+1)</tex> такследующим образом:
for <tex>x</tex> : <tex>|x| \le \log_2 n, |f_i(x)| \le \log_2 n</tex>

Навигация