функция тау
Недавно наткнулся, прыгая по ссылкам, на интересную статью (англ.; требует определенных познаний в теории сложности), из которой узнал о функции tau(n). tau(n) = наименьшее количество арифметических операций, из которых можно добраться до n, начиная с 1 и 2.
Например, если мы начнем с 1 и 2, и будем просто умножать каждый раз последнее полученное число на само себя: 1 2 4 16 256..., то за n шагов мы доберемся до числа 22n. Так что в принципе за n шагов можно добраться довольно далеко. Кроме того, тривиально добраться до самого числа n за n шагов (просто сложить 1 n раз) и даже за О(log(n)) шагов (используя двоичное разложение числа, перемножать двойки и складывать нужные разряды).
В контексте алгоритмической сложности это понятие легче рассматривать в применении к последовательностям чисел, а не одному числу. Пусть есть последовательность {xn}; скажем, что она легко вычислима, если есть многочлен p(x), так, что tau(xn) ≤ p(log(n)) для всех n. Говоря словами, последовательность легко вычислима, если вычислимость ее членов растет не быстрее, чем логарифм n (возможно, в какой-то степени).
Несмотря на то, что, вычисляя по этой модели, можно добраться за малое числое шагов довольно далеко, интуитивно говоря, "сложные" числа - содержащие в себе много информации - не будут легко вычислимы. Скажем, 2n легко вычислимо, и в это легко поверить - это всего лишь n раз двойка; а n! (n факториал) - видимо, трудно вычислить, хотя пока что никто не может это доказать (сама статья демонстрирует связь между легкой вычислимостью некоторых последовательностей, например n!, и определенными гипотезами в теории сложности арифметических цепей; я эти темы совсем почти не знаю, так что для меня это потемки).
Но особенно меня заинтересовал упомянутый вскользь факт, что если в этой модели вдобавок к сложению и умножению разрешить также деление (с остатком), то - несколько странным образом - вычислить n! становится легким делом. На этот результат есть ссылка к A. Shamir, Factoring numbers in O(log(n)) arithmetic steps. Inform. Process. Lett. 8, 28-31. У меня нет легкого доступа к этой статье; если кому-то нетрудно переслать или выложить, буду благодарен.
Например, если мы начнем с 1 и 2, и будем просто умножать каждый раз последнее полученное число на само себя: 1 2 4 16 256..., то за n шагов мы доберемся до числа 22n. Так что в принципе за n шагов можно добраться довольно далеко. Кроме того, тривиально добраться до самого числа n за n шагов (просто сложить 1 n раз) и даже за О(log(n)) шагов (используя двоичное разложение числа, перемножать двойки и складывать нужные разряды).
В контексте алгоритмической сложности это понятие легче рассматривать в применении к последовательностям чисел, а не одному числу. Пусть есть последовательность {xn}; скажем, что она легко вычислима, если есть многочлен p(x), так, что tau(xn) ≤ p(log(n)) для всех n. Говоря словами, последовательность легко вычислима, если вычислимость ее членов растет не быстрее, чем логарифм n (возможно, в какой-то степени).
Несмотря на то, что, вычисляя по этой модели, можно добраться за малое числое шагов довольно далеко, интуитивно говоря, "сложные" числа - содержащие в себе много информации - не будут легко вычислимы. Скажем, 2n легко вычислимо, и в это легко поверить - это всего лишь n раз двойка; а n! (n факториал) - видимо, трудно вычислить, хотя пока что никто не может это доказать (сама статья демонстрирует связь между легкой вычислимостью некоторых последовательностей, например n!, и определенными гипотезами в теории сложности арифметических цепей; я эти темы совсем почти не знаю, так что для меня это потемки).
Но особенно меня заинтересовал упомянутый вскользь факт, что если в этой модели вдобавок к сложению и умножению разрешить также деление (с остатком), то - несколько странным образом - вычислить n! становится легким делом. На этот результат есть ссылка к A. Shamir, Factoring numbers in O(log(n)) arithmetic steps. Inform. Process. Lett. 8, 28-31. У меня нет легкого доступа к этой статье; если кому-то нетрудно переслать или выложить, буду благодарен.