avva | функция тау

Недавно наткнулся, прыгая по ссылкам, на интересную статью (англ.; требует определенных познаний в теории сложности), из которой узнал о функции tau(n). tau(n) = наименьшее количество арифметических операций, из которых можно добраться до n, начиная с 1 и 2.

Например, если мы начнем с 1 и 2, и будем просто умножать каждый раз последнее полученное число на само себя: 1 2 4 16 256..., то за n шагов мы доберемся до числа 2^2ⁿ. Так что в принципе за n шагов можно добраться довольно далеко. Кроме того, тривиально добраться до самого числа n за n шагов (просто сложить 1 n раз) и даже за О(log(n)) шагов (используя двоичное разложение числа, перемножать двойки и складывать нужные разряды).

В контексте алгоритмической сложности это понятие легче рассматривать в применении к последовательностям чисел, а не одному числу. Пусть есть последовательность {x_n}; скажем, что она легко вычислима, если есть многочлен p(x), так, что tau(x_n) ≤ p(log(n)) для всех n. Говоря словами, последовательность легко вычислима, если вычислимость ее членов растет не быстрее, чем логарифм n (возможно, в какой-то степени).

Несмотря на то, что, вычисляя по этой модели, можно добраться за малое числое шагов довольно далеко, интуитивно говоря, "сложные" числа - содержащие в себе много информации - не будут легко вычислимы. Скажем, 2ⁿ легко вычислимо, и в это легко поверить - это всего лишь n раз двойка; а n! (n факториал) - видимо, трудно вычислить, хотя пока что никто не может это доказать (сама статья демонстрирует связь между легкой вычислимостью некоторых последовательностей, например n!, и определенными гипотезами в теории сложности арифметических цепей; я эти темы совсем почти не знаю, так что для меня это потемки).

Но особенно меня заинтересовал упомянутый вскользь факт, что если в этой модели вдобавок к сложению и умножению разрешить также деление (с остатком), то - несколько странным образом - вычислить n! становится легким делом. На этот результат есть ссылка к A. Shamir, Factoring numbers in O(log(n)) arithmetic steps. Inform. Process. Lett. 8, 28-31. У меня нет легкого доступа к этой статье; если кому-то нетрудно переслать или выложить, буду благодарен.