July 22nd, 2008

moose, transparent

функция тау

Недавно наткнулся, прыгая по ссылкам, на интересную статью (англ.; требует определенных познаний в теории сложности), из которой узнал о функции 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. У меня нет легкого доступа к этой статье; если кому-то нетрудно переслать или выложить, буду благодарен.
moose, transparent

оптимистичное (израильская политика)

А вот, например, оптимистичный взгляд на всю историю с Хизбаллой, обменом пленными, итд.; он промелькнул в комментах тематического сообщества, и показался мне стоящим того, чтобы над ним поразмыслить:

miky_m:
"У нас западное общество, со всеми его слабостями, индивидуализмом и стремлением жить нормально, но назвать Израиль слабым и всего бояшимся, когда из-за двух солдат вся страна хотела войны и возмездия и потом месяц воевала?

В израильском обществе есть солидарность, есть чувство общности судьбы, есть гордость за свой народ и есть ощущение исторической миссии. Мы здесь живем, мы сильнее всех шиитов вместе взятых на БВ, и они это знают.

Сунулись воровать солдат - получили полторы тысячи жертв, разрушенные целые деревни и районы и сотни тысяч беженцев в своей стране. Это они еще легко отделались из-за того, что здесь к войне руководство и армия не были готовы. Следующая серия будет для них пострашнее. После этого Мурнию замочили, в Сирии реактор разбомбили. До Насраллы тоже дело дойдет, как до его предшественника. Так что то, что какое-то уебище с усиками через 30 лет было выпущено в обмен на тела ничего принципиально на БВ не меняет, и они это знают. Поэтому победа для них - когда не проиграли, когда вот такой через 30 лет на митинге речь сказал, когда над родственниками павших поиздевались. Ублюдочная "победа" ублюдочных людей в своем муравейнике.

Я не считаю, что из-за этой сделки всех нужно считать пост-сионистами, что арабам вдруг некого бояться и что мы должны посыпать голову пеплом и считать себя слабее."
moose, transparent

no man is an island

Я немало размышлял последние пару дней над этой записью о Кузмине, Ахматовой, Набокове и еще о многом.

(дальше идут несколько цитат и замечаний, но интересующимся этой темой стоит вначале прочитать всю ту запись)

У меня нет особого мнения о роли Кузмина и его стихах (я плохо с ними знаком), но сама идея противопоставления "материковой" и "островной" культуры мне тут кажется все же надуманной.

"Стремясь сохранить равновесие, рассудок и дар, эта литература не желает смотреть в ту сторону, преодолевает соблазн заглянуть в мрачные бездны тоталитарной Евразии. Дабы избежать ее завораживающего гипноза, осилить засасывающий водоворот, в котором исчезли даже Платонов с Булгаковым — гениальные, но словно заколдованные Снежной Королевой тоталитарного (или антитоталитарного, что одно и то же) романтизма художники, — такая литература очерчивает вокруг себя меловую окружность."


Но ведь написал же Набоков -- и "Приглашение на казнь", и Bend Sinister... и что это значит, сказать, что Платонов исчез в водовороте? Звучит красиво, но что значит?

"Элитарность — единственное спасение, единственный путь сохранения человеческих ценностей. Путь Замятина, Оруэлла и Хаксли ведет прямиком в тоталитаризм, ибо материализовавшиеся антиутопии начинают наперебой присваивать догадки этих писателей. Антиутопия — место, которое есть. Жанр антиутопии — плоский, вульгарный реализм ХХ века, методическое пособие для созревающего диктатора. А «высокая классика» невольно становится аккомпаниатором побед и свершений параноидальных ефрейторов и недоучившихся семинаристов, драпируя их преступления в пурпур высокой трагедии и невольно обслуживая таким неправомерным завышением их честолюбие. На фоне этой сценической трагедийности островная литература кажется нетрагичной для невнимательных глаз, не замечающих, что прекрасный остров искусства (и шире — прекрасный мир) — трагичен по определению. Гармония умеет ассимилировать и растворять трагедию, переводить ее на эстетический уровень. Зримо, поверхностно трагедийна как раз дисгармоническая литература — искореженная, подмятая тоталитарным мышлением, способным разглядеть лишь сюжетно-идеологическую поверхность, но не способным проникнуть внутрь художественной структуры. [...] Одним из таких мифов оказывается, увы, и миф о «неслыханной простоте», являющейся по существу лишь более респектабельным, чуть усложненным вариантом лозунга «Искусство должно быть понятно массам». Подлинное искусство всегда элитарно, всегда пребывает внутри меловой окружности. Им движет не желание стереть эту черту, а надежда на расширение элиты, на увеличение числа людей, способных эту черту переступить. Искусство не идет к людям, оно не умеет выйти за свои собственные пределы, но оно может манить человека в себя."


Трихотомия "высокая классика", "антиутопия" и "элитарная литература" не кажется мне очень убедительной - что в ней делает антиутопия? Почему на нее отдельная атака? И куда относится, скажем, "Лолита" - не к "высокой классике" ли? Может, я просто не очень хорошо представляю себе эти предлагаемые категории.

Про элитарность - интереснее, но не убедительнее. Да, искусство не "идет к народу", но и не прячется от него специально - нет, не так, сложнее, необязательно прячется от него. Эстетизм и "искусство ради искусства" - всего лишь одна из стратегий, которая может породить гениальные книги (как у Оскара Уальда и Набокова - конечно, очень разными путями), а может - жеманную чушь; и, как обычно по закону Старджона, в 90% случаев выйдет чушь. И это нормально.
Есть, однако, и другие стратегии, приводящие к не менее "элитарным" (с точки зрения их способности подняться над 90%) результатам. Например, (простите) Шекспир.