функция тау

[avva]

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

Например, если мы начнем с 1 и 2, и будем просто умножать каждый раз последнее полученное число на само себя: 1 2 4 16 256..., то за n шагов мы доберемся до числа 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. У меня нет легкого доступа к этой статье; если кому-то нетрудно переслать или выложить, буду благодарен.

Comments

[dimrub.livejournal.com]

Factoring numbers in O(log(n)) arithmetic steps.

???

[avva.livejournal.com]

Видимо, речь идет о модели, в которой каждая арифметическая операция стоит O(1), и подсчитывается только количество операций. В реальном мире арифметика обходится нам чуть подороже :-)

[dimrub.livejournal.com]

Испугал :)

[ygam.livejournal.com]

Всё равно маловато.

[avva.livejournal.com]

Все претензии к Шамиру. Я, как видишь, даже статью не могу найти!

[dimrub.livejournal.com]

Шамир, как Тарас Бульба. "Я тебя породил..."

[amigofriend.livejournal.com]

"Я тебя парадигма..."
весь день вертится.

[eterevsky.livejournal.com]

Я точно помню, что в гугловой рассылке пробегала информация о доступе к библиотеке ACM. Думаю, там эта статья должна быть.

[avva.livejournal.com]

Там есть доступ только к журналам ACM.

[max-i-m.livejournal.com]

Статью послал.

[avva.livejournal.com]

Большое спасибо!

[dimrub.livejournal.com]

Ну так что, Шамир научился факторизировать за полиномиальное время - или можно выдыхать?

[avva.livejournal.com]

Да это статья 79-го года примерно, выдыхай :)
Результат примерно такой, как я и предполагал выше.

[spamsink.livejournal.com]

Интересно, я первый догадался проверить и послать?

[avva.livejournal.com]

Проверить и послать что?

[spamsink.livejournal.com]

Слоану.

[yury-lifshits.livejournal.com]

эта функция тау - частный случай Колмогоровской сложности
http://en.wikipedia.org/wiki/Kolmogorov_complexity

[avva.livejournal.com]

Но не очень интересный, наверное, в контексте Колмогоровской сложности? Ведь "программы" в данном случае не Тьюринг-полны.

[yury-lifshits.livejournal.com]

Тьюринг полнота тут не к селу ни к городу. Тьюринг-полнота модели вычислений X означает следующее: любую Тьюринг-вычислимую ФУНКЦИЮ можно вычислять и в модели X.

В данном случае мы говорим о порождении ОДНОЙ СТРОЧКИ. Поэтому даже самый тупой способ типа "продиктовать строку" так же полон как и машина Тьюринга.

Поэтому тау - вполне осмысленный вариант уолмогоровской сложности.

Другой известный вариант: сложность строчки = длина ее lempel-ziv encoding.

Ну и вообще, сложность строчки = размер ее архивного представления каким-нибудь стандартным архиватором.

[avva.livejournal.com]

Да, я действительно глупость сказал, спасибо :-)

[kouzdra.livejournal.com]

В том, что деление нацело упрощает факториал, нет ничего удивительного: есть известная задачка (была очень давно в 239 на одной из первых школьных олимпиад по программированию):

Написать пользуясь операциями Алгола-60 (арифметика + степень) формулу для C(n,k)

Решается просто: 10^большой степени + 1 возводится в n-ю степень - получается строка треугольника Паскаля, откуда с помощью деления с остатком вырезается нужный коэффициент. Поскольку C(n,k) с факториалом связано довольно близко - вполне вероятно, что и факториал считается.

Кстати - интересная задачка - можно ли в тех же условиях написать формулу для n!

[(Anonymous)]

Казалось бы, факториал из биномиальных коэффициентов считается уже тривиально за логарифм операций: (2n)!=C(2n,n)(n!)^2, (2n+1)!=C(2n+1,n)(n+1)(n!)^2.

[kouzdra.livejournal.com]

PS: У Кнута, кстати, очень много места во втором томе посвящено аддитивным цепочкам - это тоже самое, только с операцией сложения. Задача оценки их длинны оказывается неожиданно сложной: например быстро выплывает то, что бинарный алгоритм возведения в степень не является оптимальным - простейший пример - 15 - там он дает 6 умножений, тогда как на самом деле достаточно 5: через разложение 15=3*5

[ex-andrey-t.livejournal.com]

бинарный алгоритм возведения в степень не является оптимальным - простейший пример - 15 - там он дает 6 умножений, тогда как на самом деле достаточно 5: через разложение 15=3*5

Тут еще не учтено, что мы потратим две операции деления, для разложения числа 15 на множители.

[spamsink.livejournal.com]

Простые степени тоже поддаются этой оптимизации. Вопрос в нахождении оптимального сжатия двоичной записи числа по Лемпелю-Зиву.

[spamsink.livejournal.com]

Кстати, хорошая задача: написать программу, находящую τ(n).

[gaz-v-pol.livejournal.com]

На всероссийской олимпиаде школьников по математике когда-то меня поразила задача (автор А.Я.Канель-Белов):

Пусть ЦЛ(n) - минимальное количество применений циркуля и линейки, позволяющих увеличить данный отрезок в n раз, а Ц(n) - то же, но только циркулем (без линейки). Доказать, Ц(n)/ЦЛ(n) неограниченно (ссылка (http://rrc.dgu.ru/res/www.math.msu.su/~fpm/rus/k01/k012/k01216h.htm)).