Сложность по Арнольду

[Руст]

По ссылке Артомонова прочитал очередной доклад Арнольда о сложности последовательностей из 0 и 1 длины n. Каждая последовательность длины n есть функция из $Z_n\to Z_2$. На пространстве таких последовательности определен оператор разности Ньютона: $df(i)=f(i+1)-f(i) (mod \ 2).$ При этом для определения последнего элемента принимается f(n)=f(0) (здесь я принимаю нумерацию начиная с нулевого элемента как в компьютере).
Cудя по итерациям этого оператора Арнольд определяет сложность как количество различных элементов в последовательности функций: $f,df,ddf,d^3f,...,d^Nf,...$
В докладе для детей полученные графы он называет монадой, пренебрегая тем, что в математике этот термин уже исползуется для других целей в теории категорий (которую, как я понял он терпит не может).
Чтобы понять, что сложность по Арнольду не имеет никакого отношения к настоящей сложности, а характеизует скорее не саму последовательность а число n достаточно вычислить сложность простейшей последовательности 0 и 1 в перемежку.
Пусть последовательность определена в виде $f(k)=k(mod \ 2),k=0,1,...,n-1$
1. Вычислить сложность по Арнольду для этой последовательности.
Будет интерес у форумчан приведу здесь доказательство всех "гипотез" Арнольда на эту тему. Заранее оговаривая, что всё это не имеет никакого отношения к сложности последовательностей.
2. В качестве ещё одной простой задачи пока предлагаю, что длина дерева над каждым циклом есть

$$T_m,m=2^{2^k},k=ord_2(n).$$

[juna]

Уважаемый Руст, мой ник - Артамонов Ю.Н.

[Руст]

Прошу прощения за эту ошибку уважаемый Артамонов Ю.Н.

[Dolopihtis]

Руст писал(а):

По ссылке Артомонова прочитал очередной доклад Арнольда о сложности последовательностей из 0 и 1 длины n. Каждая последовательность длины n есть функция из $Z_n\to Z_2$. На пространстве таких последовательности определен оператор разности Ньютона: $df(i)=f(i+1)-f(i) (mod \ 2).$ При этом для определения последнего элемента принимается f(n)=f(0) (здесь я принимаю нумерацию начиная с нулевого элемента как в компьютере).
Cудя по итерациям этого оператора Арнольд определяет сложность как количество различных элементов в последовательности функций: $f,df,ddf,d^3f,...,d^Nf,...$
В докладе для детей полученные графы он называет монадой, пренебрегая тем, что в математике этот термин уже исползуется для других целей в теории категорий (которую, как я понял он терпит не может).
Чтобы понять, что сложность по Арнольду не имеет никакого отношения к настоящей сложности, а характеизует скорее не саму последовательность а число n достаточно вычислить сложность простейшей последовательности 0 и 1 в перемежку.
Пусть последовательность определена в виде $f(k)=k(mod \ 2),k=0,1,...,n-1$
1. Вычислить сложность по Арнольду для этой последовательности.
Будет интерес у форумчан приведу здесь доказательство всех "гипотез" Арнольда на эту тему. Заранее оговаривая, что всё это не имеет никакого отношения к сложности последовательностей.
2. В качестве ещё одной простой задачи пока предлагаю, что длина дерева над каждым циклом есть

$$T_m,m=2^{2^k},k=ord_2(n).$$

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

[Руст]

Это то же самое. Я просто несколько грамотнее сформулировал, то что хотел Арнольд. Любая итерация на конечном множестве через несколько шагов (не больше чем, которое указано вторым пунктом) придёт к циклу. Соответственно количество разных элементов и есть длина этого цикла плюс число ходов до цикла.

[juna]

Руст, да нет смысла обсуждать в публичном месте ошибки этого замечательного человека. Вот Вы лучше свое определение сложности придумайте в виде традиционной фирменной задачи от Руста, а мы пообсуждаем, если квалификации хватит. В теме инъективные функции Вы чем-то там подобным занимались.

[Руст]

Понятие сложности уже имеется, и я считаю нет необходимости выдумывать другие понятия.
В определении Арнольда это понятие противоречит здравому смыслу. Если некоторая последовательность простая как 1 и 0 вперемышку (второй дифференциал равен нулю если n чётное число), то при расширении (увеличивая длину на 1) хотя бы одно продолжение должна дать так же простую последовательность, что не происходит по Арнольду.

[juna]

Вы про определение сложности по Колмогорову - минимальная длина программы, порождающая эту последовательность? Тогда нужен общий алгоритм, минимизирующий длину программы, а о сложности можно говорить лишь в рамках данного алгоритма, разные минимизирующие алгоритмы будут давать разную длину для одной и той же последовательности. А глобального минимизирующего алгоритма не существует, как не существует универсального компилятора.
Интереснее связь сложности со случайностью. В той же теме "иррациональные числа и их свойства" как раз и обсуждается - можно ли считать случайной последовательностью дробную часть алгебраического или трансцендентного числа. Вы считаете, что нет, т.к. существует регулярный алгоритм получения этих последовательностей. А я бы так сказал - чем менее предсказуемая, тем хуже приближаема рациональным числом, тем ближе к равномерному закону и тем сложнее. Или еще если любую конечную последовательность в себе содержит как часть и т.д. Конечно, все это нельзя рассматривать как точные определения - так идеи и гипотезы...

[квадрат]

Целиком согласен,что всё это можно рассматривать только как гипотезы.

[Руст]

Артамонов Ю.Н. писал(а):

Вы про определение сложности по Колмогорову - минимальная длина программы, порождающая эту последовательность? Тогда нужен общий алгоритм, минимизирующий длину программы, а о сложности можно говорить лишь в рамках данного алгоритма, разные минимизирующие алгоритмы будут давать разную длину для одной и той же последовательности. А глобального минимизирующего алгоритма не существует, как не существует универсального компилятора.
Интереснее связь сложности со случайностью. В той же теме "иррациональные числа и их свойства" как раз и обсуждается - можно ли считать случайной последовательностью дробную часть алгебраического или трансцендентного числа. Вы считаете, что нет, т.к. существует регулярный алгоритм получения этих последовательностей. А я бы так сказал - чем менее предсказуемая, тем хуже приближаема рациональным числом, тем ближе к равномерному закону и тем сложнее. Или еще если любую конечную последовательность в себе содержит как часть и т.д. Конечно, все это нельзя рассматривать как точные определения - так идеи и гипотезы...

В Колмогоровском определении сложности и случайности не хватает конструктивности. Человек не может постичь "до конца" не конструктивное. Конструктивная теория сложности и случайности напрямую связана с односторонними функциями, а существование их связано с не доказанной проблемой P не равно NP. С точки зрения приложений человек не нуждается в не конструктивных определениях сложности и случайности. Я и сам здесь ратовал, что в методе Монте-Карло не требуется абстрактная случайность, а нужна хорошая равномерность. Хорошая равномерность достигается как раз простыми последовательностями типа дробной части от иррационального числа умноженного на n, а для многомерного интегрирования я предлагал брать последовательности чисел с координатами:

$$x_i=(b_1(i)/p,b_2(i)/p,...,b_k(i)/p), \ b_j(k)=a_j^k(mod \ p)$$

так чтобы периоды различных чисел a(i) были намного больше количества выбираемых N "случайных" точек. В этом смысле и Арнольд правильно заметил, что во многом наилучшей случайной последовательностью является очень простая последовательность остатков степеней по простому модулю и высказал гипотезу о самой большой сложности обратной логарифмической функции. И в приложениях "детерминированный хаос" возникает примерно так. Абстрактный "не детерминированный" и не может возникнуть. В этом смысле, я полностью на стороне Арнольда. Да и споре его с Маниным (тогда он был директором института Планка) я так же на стороне Арнольда, несмотря на то, что в своё время несколько лет был участником спецкурсов и спецсеминаров Манина. Я только против безграмотности Арнольда в вопросах элементарной теории чисел, с чем связывается "детерминированный хаос". В этой связи я полностью согласен с Арнольдом.

[juna]

Цитата:

Конструктивная теория сложности и случайности напрямую связана с односторонними функциями, а существование их связано с не доказанной проблемой P не равно NP.

Гипотеза существования односторонних функций более сильная, чем проблема $P\neq{NP}$.

[Руст]

Как понял тема не вызвала особого интереса. Поэтому изложу кратко некоторые моменты. Обозначим через Т сдвиг налево функции на один шаг. Тогда оператор d=T-1=T+1. Здесь сложение функций, соответственно и операторов производится по модулю 2 (без переноса). Соответственно $d^k=(T+1)^k=\sum_{i\in k} T^i$. Здесь в суммировании берётся все числа подчинённые k, т.е. все числа, которые в двоичной записи числа имеют нули в тех разрядах где k имеет нули, а в разрядах где k имеет 1 или нуль или 1 (всего таких чисел включая 0 2^l, где l количество не нулевых разрядов числа k). Так как T^n=T^0=1, то все степени считаются по модулю n. Учитывая, что в случае, когда n=2^k получаем: $d^{2^k}=1+T^{2^k}=1+1=0$, получаем что все функции в этом случае стабилизирубтся на нуле. Вообще если n имеет вид: $n=2^km$ с нечётным m, то через k шагов функция стабилизируется (точнее превращается в периодическую и остается такой) как периодическая с периодом m. Поэтому интересны случаи только нечётного n. После первого же действия оператора d функция становится чётной, т.е. количество единиц чётное число. Только такие функции можно интегрировать. Два возможных способа интегрирования дают две дополняющие функции (для нечётного n) т.е. одна из них чётная, а дополнение (там где нули 1 и наоборот) нечётная.
Пусть N период числа 2 по модулю n. Тогда длина цикла является делителем числа $2^N-1,(d^{2^N}=1+T^{2^N}=1+T=d).$.
Если $2^{N/2}=-1(mod \ n)$, то $d^{2^{N/2}}=1+T^{-1}=T^{-1}d$, соответственно с каждой функцией в цикл входит и любой его сдвиг.
Все функции порождаются как функция $(\sum_i T^i)g_0, g_0(0)=1,g_0(i)=0,i>0.$
Этих фактов достаточно, чтобы понять, что указанная последовательность, чередующихся 1 и нулей является самой сложной при нечётных n. Поэтому, понятие сложности по Арнольду не имеет никакого отношения к сложности, а характеризует не саму функцию, а некоторые свойства числа n и распределение степеней двоек по модулю n.
Если определять понятие сложности для конечной последовательности символов из фиксированного конечного алфабита, то необходимо соблюдать следующий принцип: при дополнении информации (продолжении) сложность последовательности не может резко уменьшаться, а может только резко возрасти для "неправильных" продолжений простых функций.

[maxal]

Рустем, во-первых, сложность по Арнольду в первую очередь определяется периодом и только потом уже числом различных элементов в последовательности $f,\partial f, \partial^2 f, \dots$

Во-вторых, я не углядел почти ничего нового по сравнению с докладом Арнольда в ММО: http://elementy.ru/lib/430178/430282
В частности, вторая из предложенных задач соответствует теореме 3 в этом докладе.

Руст писал(а):

Все функции порождаются как функция $(\sum_i T^i)g_0, g_0(0)=1,g_0(i)=0,i>0.$

Что значит "порождаются как функция"?

Руст писал(а):

Этих фактов достаточно, чтобы понять, что указанная последовательность, чередующихся 1 и нулей является самой сложной при нечётных n.

Почему именно самой сложной?

[sceptic]

Артамонов Ю.Н. писал(а):

Гипотеза существования односторонних функций более сильная, чем проблема $P\neq{NP}$.

[Руст]

maxal писал(а):

Рустем, во-первых, сложность по Арнольду в первую очередь определяется периодом и только потом уже числом различных элементов в последовательности $f,\partial f, \partial^2 f, \dots$

Во-вторых, я не углядел почти ничего нового по сравнению с докладом Арнольда в ММО: http://elementy.ru/lib/430178/430282
В частности, вторая из предложенных задач соответствует теореме 3 в этом докладе.

Руст писал(а):

Все функции порождаются как функция $(\sum_i T^i)g_0, g_0(0)=1,g_0(i)=0,i>0.$

Что значит "порождаются как функция"?

Руст писал(а):

Этих фактов достаточно, чтобы понять, что указанная последовательность, чередующихся 1 и нулей является самой сложной при нечётных n.

Почему именно самой сложной?

Как понял интерес к этой задаче появился, только я успел многое забыть.
По поводу сложности в первую очередь через период. То, что определяется для нечётных n (и я утверждаю, что в этом случае эта простая последовательность самая сложная) то дерево имеет над циклом не больше одного листа, как указано выше. поэтому здесь разницы нет (к тому же в этом случае последовательность не находится в цикле и надо сделать необходимый один шаг для попадания в цикл). Я показал, что по крайней мере для некоторых простых чисел n это действительно самый длинный цикл.
Если определяется сложность вообще (не только относительно указанной последовательности) то и в этом случае упорядочивание по длине цикла плюс шаги до этого цикла почти всегда будет совпадать с упорядочением сложности по Арнольду (лексикографический) по длине цикла в первую очередь, а потом по длине до цикла.
Что касается вопроса о конструктивной сложности я говорил об их связи с гипотезой о существовании односторонних функций. Да эта гипотеза в традиционном понимании может быть (но не обязательно) сильнее гипотезе P не равно NP. На самом деле для конструктивного построения не обязательно, чтобы обратные функции считались не по полиномипальному закону. Они могут быть расчитаны и по полиномиальному закону, но с большим показателем. Например нашли не вероятностный полиномиальный тест на простоту с показателем примерно 12 (от количества цифр). Для больших чисел уже 12 степень почти годится как односторонняя, когда функция в прямую сторону вычисляется примерно как линейная (в другую сторону).