Наборы конечных объектов с заданными информационными соотношениями между ними Вьюгин Михаил Владимирович

Содержание к диссертации

Введение

1 Информационное расстояние 18

1.1 Минимальное перекрытие с точностью дрО(1о&К(х,у)) 19

1.2 Конденсация информации 23

1.3 Минимальное перекрытие с точностью Pf)0(logd(x,y)) 26

1.4 Шенноновская и алгоритмическая теории информации . 33

2 Неделимые слова 35

3 Системы слов с большой взаимной сложностью 40

3.1 Положительный результат 41

3.2 Точность положительного результата 53

3.3 Еще одна попытка обобщить основной результат 55

4 Неупрощаемые программы 61

4.1 Игровой подход 62

4.2 Вероятностный подход 65

Используемые обозначения 68

Литература 70

• Минимальное перекрытие с точностью дрО(1о&К(х,у))
• Шенноновская и алгоритмическая теории информации
• Еще одна попытка обобщить основной результат
• Вероятностный подход

Введение к работе

Актуальность темы. А. Н. Колмогоров в работе [1] выделил три похода к определению понятия "количество информации": комбинаторный, вероятностный и алгоритмический. Вероятностный подход основан на понятии энтропии Шеннона тогда как алгоритмический - на введенном Колмогоровым понятии алгоритмической сложности. Классическая теория информации Шеннона рассматривает случайные величины, в то время как алгоритмическая теория информации Колмогорова имеет дело с индивидуальными объектами. Тем не менее, многие утверждения могут, после соответствующей переформулировки, быть перенесены из первой теории во вторую (примеры можно найти в работах [8], [11]; также см. Теорему 1.6, приведенную далее, доказанную Ан. А. Мучником и опубликованную в [9]). Получающиеся аналоги, как и все результаты теории алгоритмической сложности, имеют асимптотический характер и выполнены лишь с определенной точностью. Наилучшая возможная точность - до аддитивной константы. Однако большинство известных результатов вышеописанного типа выполнены с точностью до аддитивного члена порядка логарифма алгоритмической сложности рассматриваемых объектов.

Конечные объекты естественным образом отождествляются со своими конструктивными представлениями. Поэтому в дальнейшем мы будем говорить о конструктивных объектах.

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

Введение

Если упомянутые алгоритмические аналоги теорем классической теории информации перестают быть верными с большей точностью, можно будет сказать, что алгоритмическая теория информации является более тонким инструментом, чем шенноновская (платой за это является ее асимптотичность). Мы показываем, что это так на примере известной теоремы Вольфа-Слепяна из классической теории информации, аналог которой (Теорема 1.6) перестает быть верным с большей точностью (Теорема 1.7).

Вторая тема настоящей работы связана с определением понятия информационного расстояния между двумя конечными объектами. Ч. Беннетт, П. Гач, М. Ли, П. Витаньи и В. Цурек в статье [5], посвященной этому вопросу, рассматривают различные определения этого понятия. Одним из этих определений является длина кратчайшей программы, переводящей первый объект во второй, а второй - в первый. Авторы показывают, что всегда можно найти пару кратчайших программ, переводящих первый объект во второй, и второй - в первый соответственно, максимально "перекрывающихся", т.е. имеющих максимально возможную общую информацию (это означает, что более короткая из этих программ "содержится" в более длинной) в очень сильном смысле. В связи с этим авторы [5] ставят вопрос о минимальном перекрытии: всегда ли найдутся абсолютно независимые (имеющие нулевую общую информацию) кратчайшие программы, переводящие первый объект во второй, и второй - в первый, соответственно?

В настоящей работе дается полный ответ на этот вопрос (Теорема 1.5 и Теорема 1.1). А именно, этот вопрос имеет положительный ответ с точностью до аддитивного члена порядка логарифма сложностей объектов (Теорема 1.1). Ответ становится отрицательным с точностью до аддитивного члена порядка логарифма условных сложностей (Теорема 1.5).

Далее, в данной работе также рассматривается вопрос о существовании "неделимых" объектов, т.е. таких, для разделения которых на нетривиальные части требуется значительная дополнительная информация. Доказано, что такие объекты существуют и найдена точная нижняя оценка для их сложности (Теорема 2.1).

Следующим рассмотрен вопрос о существовании для данного фиксированного объекта такого конечного набора других объектов, который вместе с исходным объектом удовлетворял бы заранее заданному набору информационных соотношений. Этот вопрос, как и предыдущие, имеет два ва-

Введение

рианта - в зависимости от желаемой степени точности. Мы рассматриваем один частный случай данного вопроса. В этом частном случае с высокой точностью выполнен положительный результат (Теорема 3.2, а также Теорема 3.3). Мы также доказываем некоторые утверждения о невозможности усиления положительного результата в различных направлениях (разделы 3.2 и 3.3).

Последняя тема настоящей работы связана со следующим вопросом. Пусть даны два слова х и у и программа р, которая получив на вход х, выдает у. Пусть эта программа не является кратчайшей среди всех программ, переводящих х в у. Хотелось бы узнать, всегда ли можно найти более короткую программу р^г, также переводящую х в у, простую при известной программе р. Существование такой р' означало бы "упрощаемость" программы р, т.е. этот вопрос можно назвать вопросом о существовании "неупрощаемых" программ. Мы доказываем, что такие примеры существуют (Теорема 4.1). Приводятся различные доказательства этого факта.

Методы исследования. В работе применяются методы теории алгоритмов и игровые методы.

Научная новизна. Все основные результаты работы являются новыми и состоят в следующем:

1. Исследован вопрос о существовании независимых программ, переводящих конструктивные объекты друг в друга. Решена задача о минимальном перекрытии, поставленная в [5].

2. Получена нижняя оценка для точности, с которой выполнен алгоритмический аналог теоремы Вольфа-Слепяна из классической теории информации.

3. Доказано существование объектов, деление которых на нетривиальные части требует большой дополнительной информации ("неделимых" объектов).

4. Рассмотрен вопрос о существовании для данного объекта наборов других объектов, которые бы удовлетворяли заданным информационным соотношениям. Получены результаты в некоторых важных частных случаях.

Введение 5

5. Доказано существование избыточных по длине программ, которые не задают более короткой программы, решающей ту же задачу ("неупрощаем ых" программ).

Приложения. Работа носит теоретический характер. Полученные результаты относятся к теории колмогоровской сложности и могут применяться в алгоритмической теории информации.

Апробация работы. Основные результаты настоящей диссертации докладывались на следующих семинарах и конференциях:

научно-исследовательском семинаре по математической логике в МГУ под руководством академика РАН проф. С. И. Адяна и проф. В. А. Успенского;

семинаре "Колмогоровский семинар по сложности вычислений и сложности определений" под руководством Н. К. Верещагина, А. Е. Ромащенко, А. Л. Семенова и А. X. Шеня;

международной конференции 15th Annual IEEE Conference on Computational Complexity в 2000 г;

конференции "Ломоносовские чтения" в МГУ им. М. В. Ломоносова в 2000 г;

XXII Конференции молодых ученых механико-математического факультета МГУ им. М. В. Ломоносова в 2000 г;

XXI Конференции молодых ученых механико-математического факультета МГУ им. М. В. Ломоносова в 1999 г.

Публикации. Основные результаты диссертации опубликованы в работах [12, 13, 14, 15].

Для полноты изложения в диссертации приводятся без доказательств Теорема 1.6 и Теорема о преобразовании, не принадлежащие автору. Первый из этих результатов получен Ан. А. Мучником и опубликован в работе [9]. Второй результат получен Ч. Беннетом, П. Гачем, М. Ли, П. Витаньи и В. Цуреком и опубликован в работе [5]. Также в главе 4 приведено вероятностное доказательство Теоремы 4.1, принадлежащее Ан. А. Мучнику.

Введение

Структура работы. Работа состоит из введения, 4 глав, списка используемых обозначений и списка литературы, содержащего 15 наименований. Общий объем диссертации - 71 страница.

Теоремы и леммы нумеруются независимо. Номер состоит из номера главы и номера утверждения в ней. Номера теорем в предисловии совпадают с номерами тех же теорем в основном тексте диссертации.

Опишем кратко содержание работы. Во введении дан краткий обзор работ, связанных с темой диссертации, и сформулированы основные результаты диссертации.

Колмогоровская, или алгоритмическая, сложность слов была введена в 1965 году в работе А. Н. Колмогорова [1]. Пусть х иу- двоичные слова (конечные последовательности нулей и единиц). Неформально, колмогоровская сложность у относительно х определяется как длина самой короткой программы, которая получая на вход слово ж, выдает слово у.

Будем называть способом программирования любую частичную вычислимую функцию двух аргументов А (аргументы и значения А - двоичные слова). Значение А(р, х) будем интерпретировать как результат работы программы р на входе х. Если А(р, х) не определено, то будем говорить, что при способе программирования А программа р на входе х не выдает никакого результата. Теперь мы можем определить колмогоровскую сложность слова у относительно слова х при способе программирования А как:

^{

min |р| , если существует такое р, что А(р, х) = у, А(р,х)=у со , если нет такого р, что А(р, х) = у.

Надо обратить внимание на то, что определяемая таким образом сложность зависит от выбора способа программирования. Важным открытием Колмогорова стало существование оптимального способа программирования. Сформулируем данное утверждение точно. Будем говорить, что способ программирования А не хуже, чем способ программирования В, если

БСУх,уК_А(у\х)^К_в(у\х) + С.

Согласно [1] существует оптимальный способ программирования, т. е. способ программирования С/, который не хуже любого другого.

Оптимальный способ программирования не единствен. Если Uq и U\ -два оптимальных способа программирования, то они отличаются лишь на

Введение

ограниченную величину:

3CVx_}y\K_Ul{y\x)-K_Uo(y\x)\^C,

т. е. асимптотически колмогоровские сложности относительно разных оптимальных способов программирования ведут себя одинаково. Некоторые оптимальные способы программирования могут иметь те или иные особые свойства. Однако в данной работе мы не будем интересоваться различиями между оптимальными способами программирования. Поэтому мы можем зафиксировать любой из них (назовем его U). В дальнейшем будем рассматривать только колмогоровскую сложность относительно выбранного оптимального способа программирования: Ки{у\х). При этом мы будем опускать индекс U, т. е. будем пользоваться обозначением

К(у\х) := Ки(у\х).

Величину К(у\х) будем называть колмогоровской сложностью слова у относительно слова х (или колмогоровской сложностью слова у при известном слове х). Заметим, что для любых х, у условная сложность К{у\х) конечна.

Колмогоровской сложностью слова х назовем сложность х относительно пустого слова. Колмогоровскую сложность х будем обозначать К(х):

К{х) := К(х\А).

Кроме колмогоровской сложности слов будем рассматривать колмогоровскую сложность кортежей слов. Для этого мы должны выбрать некоторую вычислимую нумерацию всех кортежей слов, т. е. вычислимую биекцию между множеством всех кортежей двоичных слов и множеством двоичных слов. В выборе такой нумерации, так же как и в выборе оптимального способа программирования, имеется значительный произвол. Зафиксировав некоторую нумерацию кортежей, назовем колмогоровской сложностью кортежа слов (уi,..., у_п) относительно кортежа слов (#1,...,х_т) колмогоровскую сложность номера первого кортежа относительно номера второго кортежа. Данную сложность мы будем обозначать K(yi,..., y_n\xi,..., х_т). Ясно, что смена нумерации кортежей изменит колмогоровские сложности кортежей лишь на ограниченную величину.

Заметим, что для любого конечного алфавита А можно определить колмогоровскую сложность слов в данном алфавите (а также колмого-

Введение

ровскую сложность кортежей слов в данном алфавите), выбрав произвольную нумерацию букв алфавита Л. Конечные объекты естественным образом отождествляются со своими конструктивными представлениями. Поэтому в дальнейшем мы будем говорить о конструктивных объектах. Аналогично вышесказанному, можно говорить о колмогоровской сложности произвольных конструктивных объектов: конечных графов, элементов конечных полей, подпространств в конечномерном линейном пространстве над конечным полем и т. д., если выбрать вычислимую нумерацию данных объектов. При этом изменение нумерации приведет к изменению колмого-ровских сложностей рассматриваемых объектов лишь на ограниченную величину. Говоря о колмогоровской сложности тех или иных конструктивных объектов, мы всегда будем подразумевать, что для них зафиксирована некоторая вычислимая нумерация.

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

1(х:у):=К(х) + К{у)-К(х,у).

Необходимо отметить, что данное определение отличается от оригинального определения Колмогорова (они равносильны с точностью до аддитивного члена вида 0(logK(x,y)), однако не до 0(1(х : у))). Взаимная информация х и у показывает, насколько знание одного из этих слов упрощает задачу нахождения другого.

Назовем слова х и у независимыми если их взаимная информация 1{х : у) близка к 0. Это определение неформально и в каждом конкретном случае необходимо уточнять понимание "близости".

Перечислим кратко другие важные свойства колмогоровской сложности и взаимной информации, которыми мы будем пользоваться в дальнейшем (подробнее см. [7] или [4]).

Существует константа с такая, что для любого числа / число слов х
со сложностью К{х) ^ I меньше числа 2^l+1 и не меньше числа 2¹~^с:

2¹~^с < #{х\К(х) < 1} < 2^l+1. (1)

К(х) ^ (х) + 0(1), где (х) - длина слова х (список всех используе
мых обозначений можно найти на странице 68)¹.

¹ Это утверждение является более короткой записью следующего утверждения: ЭсУх К(х) ^ (х) +

Введение

К(х\у)^К(х) + 0(1).

Для любой вычислимой функции f{x) найдется константа с такая, что K(f(x)) ^ К{х) + с для всех х, на которых / определена.

Выполнены неравенства

К(х,у) < К(х) + К(у\х) + 2logК(у\х) + 0(1), tffoy) ^ #(*) +ДГ(ф) +2 log ДГ(а;) +0(1)

для всех х, у (заметим, что члены 2 log К{у\х) и 2 log К(х) появляются здесь из-за необходимости закодировать пару программ с помощью одной программы).

К{х, у) > К(х) + К(у\х) - 0(logК(х, у)),

а значит \К(х,у) — К(х) — К(у\х)\ = 0(logK(x,y)).

I(x:y)Z-0(\ogK(x\y))_t
I(x:y)^-0(\ogK(y\x)).

Договоримся называть слово х случайным или несжимаемым если его колмогоровская сложность К{х) близка к (х) где {х) - длина х. Это определение неформально и нуждается в уточнении в каждом случае. Оно отвечает интуитивному пониманию случайности так как из первых двух вышеприведенных свойств следует, что большинство слов любой фиксированной длины случайны.

Если слово х несжимаемо, то и любой префикс х' слова х также
несжимаем, а именно

{х') - К{х') ^ 1{х) - К(х) + 21og(z') + 0(1).

Если р - самая короткая программа вычисляющая у по данному х, то
р несжимаема, а именно

К{р) = Цр) + 0(1) = К{у\х) + 0(1).

с. В дальнейшем везде, где это возможно, мы будем использовать более короткую запись.

Введение

На этом мы закончим необходимый обзор теории колмогоровской сложности и перейдем непосредственно к теме данной работы.

Результаты настоящей работы можно разделить на несколько групп.

Главной темой Главы 1 является рассмотрение вопросов, связанных с понятием информационного расстояния.

Колмогоровская сложность является общепринятой мерой количества информации, содержащегося в индивидуальном конструктивном объекте. Хотелось бы определить подобную же меру для информационного расстояния между двумя объектами. Ч. Беннетт, П. Гач, М. Ли, П. Витаньи и В. Цурек в статье [5] рассматривают несколько естественных определений меры информационного расстояния и доказывают, что эти определения эквивалентны в сильном смысле.

Интуитивно, информационное расстояние между словами х и у равно минимальному количеству информации, достаточному для того, чтобы вычислимо по х восстановить у и наоборот, вычислимо по у восстановить х. Чтобы быть расстоянием, такая мера D(x, у) должна удовлетворять аксиомам:

D(x, у) = 0 если и только если х = у;

D(x,y) + D(y,z) ^ D(x,z) (неравенство треугольника);

D(x,y) = D(y,x) (симметричность).

Следуя [5], рассмотрим две возможные формализации этого понятия. Первой естественной мерой информационного расстояния между словами х иу является длина кратчайшей программы, которая получая на вход х, дает у и, обратно, получая на вход у, дает х. Обозначим эту меру d\(x, у).

Указанная кратчайшая программа должна воспользоваться имеющейся "общей частью" информации, необходимой для перехода от х к у и информации, необходимой для перехода от у к х. Хотелось бы знать, в каких пределах информация, необходимая для перехода от х к у может быть выбрана "перекрывающейся" с информацией, необходимой для перехода от у к я. В некоторых простых случаях может быть достигнуто полное перекрытие так, что одна и та же кратчайшая программа позволяет переходить как от х к у, так и наоборот. Например, если х и у - независимые случайные слова одинаковой длины п (с точностью до аддитивной константы К(х\у) = К(у\х) = п), то их побитовое исключающее "или" х у

Введение 11

является искомой кратчайшей программой для обоих вычислений (х при известном у и у при известном х).

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

К{у\х) > К(х\у).

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

Прежде чем сформулировать главный результат работы [5], определим еще одну меру информационного расстояния между словами х, у как

d(x,y) = тах{К(х\у),К(у\х)}.

В дальнейшем информационным расстоянием мы будем именовать величину d(x,y). Очевидно, что с точностью до аддитивного члена вида 0(\ogd(x,y)) выполнены неравенства

d(x,y) < di(х, у) ^ К(х\у) + К(у\х) < 2d(x,y).

Можно было бы предполагать, что в худшем случае перекрытие оказывается нулевым, то есть достигается равенство d\(x, у) = К(х\у)+К(у\х) + 0(\ogd(x,y)), причем К(х\у) + К(у\х) значительно превосходит d(x,y). Однако оказывается, что для любых слов х, у выполнено равенство

d\{x,y) = d(x,y) + 0(logd(x,y)).

Это утверждение является прямым следствием следующей теоремы.

Теорема о преобразовании [5]. Пусть слова х,у таковы, что К(у\^х) ^ К{^х\у)- Тогда найдутся слово d длины К{у\х) — К{х\у) и программа г длины К(х\у) + 2К({К(х\у), К{у\х))) + 0(1), которая получив на вход xd дает у и обратно, получив на вход у дает xd.

Эта теорема утверждает существование кратчайших программ р и q, переводящих х в у, а у в х соответственно, "перекрывающихся" максимальным возможным способом. Действительно, имея р = (г, {d)) и у, мы можем вычислить х, а имея q = (r,d) их мы вычислим у.

Введение

В настоящей работе мы рассмотрим противоположный вопрос: всегда ли упомянутые кратчайшие программы р и q могут быть выбраны полностью независимыми, а именно, такими что взаимная информация I(p : q) близка к нулю. То есть, правда ли, что для каждой пары слов х, у найдутся программы р и q такие, что U(p,x) = у, U(q,y) = х, (р) та К(у\х), (q) та К{х\у) и 1{р : q) та О (где приблизительные равенства выполнены с точностью до аддитивного члена вида 0(\ogd(x,y)))7 Эта задача была поставлена в [5].

Ниже мы покажем, что ответ на этот вопрос отрицателен. Более того, существует пара слов х, у, для которых любые две программы минимальной длины, р, q, переводящие х в у и обратно, соответственно, имеют максимальное перекрытие, то есть K(p,q) = d(x,y) + 0(\ogd(x,y)).

Теорема 1.5. Для любого d найдется с такое, что для всех п выполнено следующее. Существуют слова х, у такие, что

п ^ К(х\у),К(у\х) < п + 2 log log п + с

и для всех слов p,q с длинами менее n + dlogn и таких, что U(p,x) = у, U{q, у) = х, выполнено неравенство

K(p,q)

Однако, если потребовать чтобы равенства (р) та К(у\х), (q) та К(х\у), 1{р : q) та О выполнялись с точностью до аддитивного члена вида О (log К ((х, у})) (вместо 0(}ogd(x, у))), ситуация изменится кардинальным образом. В этом случае всегда найдется пара независимых программ

Р,Я-

Теорема 1.1. Для любых двух слов х, у найдутся программы р и q такие, что U{p,x) = у, U(q,y) = х, {р) та К(у\х), (q) та К(х\у), и 1{р : q) та О (где приблизительные равенства выполнены с точностью до аддитивного члена вида 0(\ogK(x,y))).

В разделе 1.4 мы рассмотрим вопрос о связи между шенноновской и алгоритмической теориями информации.

Между шенноновской теорией информации и теорией колмогоровской сложности имеется сильный параллелизм. Некоторые теоремы шенноновской теории информации имеют аналоги в теории колмогоровской сложности (см. например [2], [11], [8]). Одним из таких результатов является следующая теорема, доказанная Ан. А. Мучником.

Введение

Теорема 1.6 (Ан. А. Мучник). Для любых слое х и у найдется слово р такое, что

i(p) « К(у\х), (2)

К(у\х,р) и 0, (3)

К(р\у) « 0, (4)

где приблизительные равенства выполняются с точностью до аддитивного члена вида 0(}ogK(y)).

То есть для любой пары слов х,у найдется кратчайшая программа р, переводящая х в у, простая относительно у.

Эта теорема является прямым аналогом теоремы Вольфа-Слепяна из шенноновской теории информации [3].

Однако Теорема 1.6 бессодержательна (т.е. очевидна) в случае когда слова х и у отличаются мало, например когда К(у\х) имеет порядок 0(log К(у)). Хотелось бы узнать, можно ли усилить теорему так, чтобы приблизительные равенства выполнялись с большей точностью, зависящей только от К(у\х).

В настоящей работе мы даем отрицательный ответ на этот вопрос. А именно, верна следующая

Теорема 1.7. Теорема 1.6 перестает быть верной, если потребовать выполнения приблизительных равенств (2)-(4) с точностью до аддитивного члена вида 0(}ogK(y\x)).

Из этого отрицательного результата в частности следует, что алгоритмическая теория информации богаче и в некоторых случаях является более тонким инструментом, чем шенноновская теория информации. Платой за это является асимптотический характер алгоритмической теории информации.

В Главе 2 рассматривается вопрос о "разделении"информации.

Рассмотрим следующий вопрос. Зафиксируем числа а и /3 такие, что а>0, /3>0иа + /? = 1. Можно ли произвольное слово х разделить в пропорции а : /3? Формально это означает: верно ли, что для любого слова х найдется слово у такое, что

К{у\х) « О,

К (у) « аК(х), К{х\у) « РК(х).

Введение

Этот вопрос, как и предыдущие, имеет разные варианты в зависимости от желаемой степени точности. Легко видеть, что с точностью до 0(}ogK(x,y)) ответ положителен. Достаточно перейти от слова х к кратчайшей программе, вычисляющей х и взять в качестве у начальный кусок этой программы длины аК{х). Можно было бы предположить, что результат остается верным и при точности 0(1), однако это не так. Из следующей теоремы следует отрицательный ответ при точности \ log log К(х).

Теорема 2.1. Существует константа с > О такая, что для любого натурального числа к существует слово х такое, что К(х) ^ 3k, и удовлетворяющее условию: для любого слова у, если К(у\х) < к, то либо

К (у) <к + с

либо

К(х\у) <к + с.

Длина слова х равна 2>к2² . При этом, существует константа с\ такая, что для каждого х удовлетворяющего вышеприведенному условию, выполнено

К{х)>2^2к~^с\

Число таких х-ов конечно.

Эта теорема утверждает существование слова х, неделимого ни в какой пропорции. Любое слово у, простое относительно х либо просто абсолютно, либо мало отличается от х. Она также дает нижнюю оценку на сложность такого примера.

В Главе 3 мы рассмотрим следующий общий вопрос. Для данного слова о мы хотим подобрать слова х\,Х2,... ,х_т так, чтобы набор слов xq,xi, ... ,х_т удовлетворял заранее заданным информационным соотношениям. В общем виде такой вопрос очень сложен и мы дадим ответы на некоторые из его частных случаев.

Начнем со следующего частного вопроса. Верно ли, что для всякого числа п и слова х такого, что К{х) ^ п можно найти слово у для которого

К(х\у) « п, К(у\х) « п. (5)

Легко доказать, что с точностью до аддитивного члена вида 0(}ogK(x)) ответ на этот вопрос положителен (Теорема 3.1), такое слово у всегда найдется. Но можно ли усилить это утверждение? В отличие от приведенных

Введение

выше случаев, это сделать можно для точности O(logn), а в большинстве случаев даже до 0(1). А именно верна следующая

Теорема 3.2. Существует константа с такая, что для любого п выполнено следующее: для любого слова х удовлетворяющего условию К(х) ^ 2п + с, найдется слово у такое, что обе условные сложности К{х\у) и К(у\х) располагаются между п и п-\- с:

п < К(х\у),К{у\х) ^п + с.

Эта теорема не покрывает случая п ^ К(х) ^ 2п, в котором однако можно применить уже упомянутую Теорему 3.1 и получить результат с точностью O(logn).

Оба приведенных результата можно обобщить на случай любого конечного множества слов. В несколько ослабленном виде их можно сформулировать в одном утверждении.

Теорема 3.4. Для каждого числа т найдется константа с такая, что для всякого п и всякого двоичного слова хо такого, что K(xq) > п выполнено следующее: существует набор слов xi,..., х_т удовлетворяющий условию

\K{xi\xj) — п\ < 5 log п-\- с, О ^ i, j ^ га, і ф j.

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

Теорема 3.7. Пусть даны число п и слово хо такие, что K(xq) ^ п. Тогда найдутся слова х\ и Х2 такие, что

K(xi\xj) и га, i,j Є {0,1,2}, г ф j, K(xi\xj,x_k) wn, i,j,k Є {О,1,2}, г 7^ j фк,іфк,

где приблизительные равенства выполнены с точностью до аддитивного члена вида 0(\ogK(xo)).

Встает вопрос: можно ли ее усилить, потребовав точности O(logn)? Из следующей теоремы следует отрицательный ответ на этот вопрос.

Теорема 3.8. Существует константа с, для которой выполнено следующее. Пусть га и d - произвольные целые числа. Существует слово xq

Введение 16

такое, что K(xq) ^ n + d и нет слое х\ и Х2, удовлетворяющих следующим неравенствам:

К(xi\xo) ^n + d,i Є {1,2},

K(x_Q\xi) > d + 21ogn + c,i Є {1,2},

К(х2\хо, Х\) > п + 2 logd.

Минимальное перекрытие с точностью дрО(1о&К(х,у))

На этом мы закончим необходимый обзор теории колмогоровской сложности и перейдем непосредственно к теме данной работы. Главной темой Главы 1 является рассмотрение вопросов, связанных с понятием информационного расстояния.

Колмогоровская сложность является общепринятой мерой количества информации, содержащегося в индивидуальном конструктивном объекте. Хотелось бы определить подобную же меру для информационного расстояния между двумя объектами. Ч. Беннетт, П. Гач, М. Ли, П. Витаньи и В. Цурек в статье [5] рассматривают несколько естественных определений меры информационного расстояния и доказывают, что эти определения эквивалентны в сильном смысле.

Интуитивно, информационное расстояние между словами х и у равно минимальному количеству информации, достаточному для того, чтобы вычислимо по х восстановить у и наоборот, вычислимо по у восстановить х. Чтобы быть расстоянием, такая мера D(x, у) должна удовлетворять аксиомам: D(x, у) = 0 если и только если х = у; D(x,y) + D(y,z) D(x,z) (неравенство треугольника); D(x,y) = D(y,x) (симметричность). Следуя [5], рассмотрим две возможные формализации этого понятия. Первой естественной мерой информационного расстояния между словами х иу является длина кратчайшей программы, которая получая на вход х, дает у и, обратно, получая на вход у, дает х. Обозначим эту меру d\(x, у). Указанная кратчайшая программа должна воспользоваться имеющейся "общей частью" информации, необходимой для перехода от х к у и информации, необходимой для перехода от у к х. Хотелось бы знать, в каких пределах информация, необходимая для перехода от х к у может быть выбрана "перекрывающейся" с информацией, необходимой для перехода от у к я. В некоторых простых случаях может быть достигнуто полное перекрытие так, что одна и та же кратчайшая программа позволяет переходить как от х к у, так и наоборот. Например, если х и у - независимые случайные слова одинаковой длины п (с точностью до аддитивной константы К(х\у) = К(у\х) = п), то их побитовое исключающее "или" х у является искомой кратчайшей программой для обоих вычислений (х при известном у и у при известном х). Рассмотрим теперь случай когда одно из этих вычислений требует больше информации, чем другое, например, В этом случае кратчайшие программы не могут быть выбраны равными из-за разности их длин. В некоторых случаях перекрытие тем не менее может быть сделано полным в том смысле, что большая программа должна содержать всю информацию, содержащуюся в меньшей, наряду с некоторой дополнительной информацией. Прежде чем сформулировать главный результат работы [5], определим еще одну меру информационного расстояния между словами х, у как В дальнейшем информационным расстоянием мы будем именовать величину d(x,y). Очевидно, что с точностью до аддитивного члена вида 0(\ogd(x,y)) выполнены неравенства Можно было бы предполагать, что в худшем случае перекрытие оказывается нулевым, то есть достигается равенство d\(x, у) = К(х\у)+К(у\х) + 0(\ogd(x,y)), причем К(х\у) + К(у\х) значительно превосходит d(x,y). Однако оказывается, что для любых слов х, у выполнено равенство d\{x,y) = d(x,y) + 0(logd(x,y)). Это утверждение является прямым следствием следующей теоремы. Теорема о преобразовании [5]. Пусть слова х,у таковы, что К(у\х) К{Х\У)- Тогда найдутся слово d длины К{у\х) — К{х\у) и программа г длины К(х\у) + 2К({К(х\у), К{у\х))) + 0(1), которая получив на вход xd дает у и обратно, получив на вход у дает xd. Эта теорема утверждает существование кратчайших программ р и q, переводящих х в у, а у в х соответственно, "перекрывающихся" максимальным возможным способом. Действительно, имея р = (г, {d)) и у, мы можем вычислить х, а имея q = (r,d) их мы вычислим у. Введение В настоящей работе мы рассмотрим противоположный вопрос: всегда ли упомянутые кратчайшие программы р и q могут быть выбраны полностью независимыми, а именно, такими что взаимная информация I(p : q) близка к нулю. То есть, правда ли, что для каждой пары слов х, у найдутся программы р и q такие, что U(p,x) = у, U(q,y) = х, (р) та К(у\х), (q) та К{х\у) и 1{р : q) та О (где приблизительные равенства выполнены с точностью до аддитивного члена вида 0(\ogd(x,y)))7 Эта задача была поставлена в [5]. Ниже мы покажем, что ответ на этот вопрос отрицателен. Более того, существует пара слов х, у, для которых любые две программы минимальной длины, р, q, переводящие х в у и обратно, соответственно, имеют максимальное перекрытие, то есть K(p,q) = d(x,y) + 0(\ogd(x,y)). Теорема 1.5. Для любого d найдется с такое, что для всех п выполнено следующее. Существуют слова х, у такие, что и для всех слов p,q с длинами менее n + dlogn и таких, что U(p,x) = у, U{q, у) = х, выполнено неравенство

Однако, если потребовать чтобы равенства (р) та К(у\х), (q) та К(х\у), 1{р : q) та О выполнялись с точностью до аддитивного члена вида О (log К ((х, у})) (вместо 0(}ogd(x, у))), ситуация изменится кардинальным образом. В этом случае всегда найдется пара независимых программ Теорема 1.1. Для любых двух слов х, у найдутся программы р и q такие, что U{p,x) = у, U(q,y) = х, {р) та К(у\х), (q) та К(х\у), и 1{р : q) та О (где приблизительные равенства выполнены с точностью до аддитивного члена вида 0(\ogK(x,y))).

Шенноновская и алгоритмическая теории информации

Пусть х есть произвольное слово. Если мы пожелаем "сжать" его, мы можем рассмотреть кратчайшую программу х , вычисляющую х. Тогда К(х\х ) = 0(1) и К{х \х) = 0(\ogK(x)). (Действительно, х может быть восстановлено по х без дополнительной информации; чтобы получить х по х достаточно знать длину х , т.е., К(х), что потребует 0(logK(x)) битов.) Также легко видеть, что х несжимаемо (т.е. "случайно"), его сложность близка к его длине: К(х ) = (х ) + 0{1). Таким образом, для каждого х найдется случайное слово х такое, что условная сложность К(х \х) мала и длина х равна К(х).

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

Предложение 1.1. Для каоюдого слова х и для каоюдого целого числа I К(х) найдется слово z длины I такое, что \K(z) — / 2 logZ + 0(1) и K(z\x) log К{х) + 2 log I + O(l).

Однако верхняя граница K(z\x) в этом утверждении достаточно слабая (особенно если К(х) намного больше I); хотелось бы получить границу, зависящую только от /, а не от К(х), например O(logZ). Зафиксируем некоторую константу d. Нам хотелось бы знать, для каких пар (т, I) выполнено следующее: для любого слова х сложности К{х) — т найдется z длины / такое, что K(z\x) dlog/ и K(z) I — dlogl. Предложение 1.1 показывает, что пара (m, I) обладает этим свойством если т ограничено полиномом от /. (Более точно, если d 2, достаточно т — 0(ld 2) чтобы гарантировать, что K(z\x) ограничено dlogl.) Такое z существует также для очень больших т. Пусть т так велико, что из равенства К(х) = т следует, что х превосходит максимальное время, необходимое для окончания работы U(p, Л) для всех р длины не больше I (здесь мы отождествляем х с его номером в некотором вычислимом перечислении всех слов). Тогда имея х и I мы можем получить список всех слов со сложностью, меньшей I и выбрать такое слово z длины I, которое не входит в список. Теорема 1.2 утверждает, что для промежуточных значений т существование z не гарантировано. Теорема показывает, что для некоторых т (и для некоторых х), любое слово, простое при условии х, просто безусловно, а значит не может быть случайным. Теорема 1.2. Существует константа с такая, что для любых k, I, т найдется слово х со следующими свойствами: и каждое слово z такое, что t{z) I, K(z\x) к, безусловно просто: K(z) k + 2K{m,l\k) + c. Доказательство. Мы ищем слово х длины N = m + 2k{l + 1) такое, что все -простые (по отношению к х) слова z длины меньшей I (безусловно) просты. Рассмотрим двудольный граф, левосторонними вершинами которого являются слова длины меньшей Z, а правосторонними - слова длины N. Слово z из левой доли соединено ребром со словом х из правой доли если K(z\x) к. Каждая вершина х из правой доли имеет входную степень меньше 2к.

Будет удобно использовать следующую метафору: Противник перечисляет ребра, т.е., пары (z, х) такие, что K(z\x) к. Мы можем объявить некоторый z "простым", присвоив ему простое описание. Конечно, число z, которые могут быть таким образом объявлены простыми, ограничено (это число не превзойдет 2к).

Наша цель состоит в том, чтобы гарантировать наличие "хорошего" х в следующем смысле: все z, объявленные Противником простыми относительно х, объявлены нами (безусловно) простыми. Для доказательства теоремы нам необходимо иметь много хороших слов х: если мы имеем 2т хороших слов, то некоторое хорошее слово х имеет сложность не меньшую т (как это и требуется в формулировке теоремы).

Опишем нашу стратегию. На первом шаге мы подождем до тех пор, пока как минимум 2 — 2т правосторонних вершин не окажутся соединены с некоторыми левосторонними вершинами. (Если этого так и не произойдет, мы добиваемся своей цели так как оставшиеся 2т вершин являются хорошими.) После этого мы выбираем слово z\ длины меньшей I, которое соединено с как минимум (2 — 2т)/2 различных слов х.

После появления такого z\, мы объявляем его "простым", и в дальнейшем рассматриваем только правосторонние вершины, соединенные с z\ в этот момент. Назовем эти вершины 1-вершинами. Получится как минимум (2 — 2m)/2 2N (l+1) 1-вершин. Затем мы подождем до тех пор, пока как минимум 2ЛГ (І+1) —2т 1-вершин окажутся соединены (Противником) с левосторонними вершинами, отличными от z\. Тогда мы выберем вершину %г ф z\, соединенную с как минимум (2N (l+1) — 2т)/2 1-вершин.

Объявим z i простой, и в дальнейшем будем рассматривать только вершины, соединенные с Z2. Такие вершины назовем 2-вершинами. Имеется как минимум (2 +1) - 2т)/2г 2N 2V+l 2-вершин.

После того, как вышеописанная процедура была применена s раз, вершины z\,...,zs объявлены простыми, и есть как минимум 2 s( +1) s-вершин (мы предполагаем, что N — s(l + 1) 0); каждая s-вершина соединена с z\,...,zs. Но может оказаться, что для некоторого s число s-вершин, соединенных с какой-либо вершиной помимо zi,... ,zs, окажется меньше 2 -s( +1) — 2m. В этом случае мы добиваемся своей цели так как окажется как минимум 2т хороших вершин. Остается заметить, что так как N = т + 2к{1 + 1), то это и должно произойти для некоторого s 2к, иначе окажется 2 -вершина, соединенная с 1,..., что противоречит нашему предположению.

Остается показать, откуда получается верхняя оценка K(z) к + 2К(т, l\k)-\-c для любого z, объявленного нами простым. Действительно, вышеописанная процедура вычислима и задана параметрами т, к, I; чтобы задать Z{ нам нужно знать еще только значение г, которое не превосходит 2к, а значит может быть задано словом длины в точности равной к (можно дополнить недостающие позиции нулями слева). Имея это слово, мы знаем одновременно і и к, после чего находим га, I применяя к к программу, вычисляющую m, I по к. (Множитель 2 необходим для кодирования пары: К (u, v) К (и) + 2K(v) + 0(1).)

Вспомним, с чего мы начали. Мы хотели показать, что для промежуточных значений га найдутся х с К{х) — т, для которых пет случайных 2, простых относительно х. Чтобы формализовать эту цель, зафиксируем d и назовем слово z длины / случайным если K(z) I — dlogl. Назовем слово простым относительно х если K(z\x) dlogl. Взяв в доказанной выше теореме k = dlogl, мы получим

Еще одна попытка обобщить основной результат

То есть, все элементы Мп имеют сложность, не превышающую 2п + 0(1). Действительно, каждый элемент Мп может быть задан словом длины 2п + 4 (соответствующим порядковому номеру, с каким он появляется в перечислении Мп); заметим, что длины этих слов задают п (если их дополнить нулями слева) и поэтому нет необходимости задавать п отдельно.

Аналогично, множество С(п, х) всех вершин, соединенных с некоторой вершиной х ненаправленными ребрами, может быть эффективно перечислено (при известных п и х) и содержит не более 2П+2 элементов, а значит, любая вершина у соединенная с х ненаправленным ребром может быть задана (при известном х) словом длины п -f 2. Таким образом, для любого ненаправленного ребра (р, q) мы имеем K(p\q) п + 0(1) и K(q\p) n + 0(1).

Требование (3) говорит, что каждая вершина х либо отмечена (и тогда К(х) 2п + 0(1)), либо есть другая вершина у, соединенная с х ненаправленным ребром (т.е. К{у\х) п 4- 0(1) и К{х\у) п + 0(1)), но не соединенная с х направленным ребром, идущем в каком-либо направлении (а это значит К(х\у) пи К(у\х) п).

Теорема 3.2 доказана (по модулю Леммы 3.1). Доказательство Леммы 3.1. Для описания выигрывающей стратегии для Математика нам нужно дать некоторые определения. Мы будем говорить, что ненаправленное ребро (х, у) (где х Є X, у Є Y) покрыто слева если есть направленное ребро (х, у), идущее слева направо; ребро (х, у) покрыто справа если есть направленное ребро (у, х) идущее справа налево. Заметим, что ребро может быть покрыто и справа и слева одновременно. Вместе покрытые справа или слева ненаправленные ребра называются покрытыми (имеются в виду ненаправленные) ребрами; остальные ненаправленные ребра называются непокрытыми. Выигрывающая стратегия сохраняет некоторые "инвариантные свойства" после хода Математика:

Непокрытые ребра задают взаимно-однозначное соответствие между некоторыми подмножествами X С X и У С У.

Заметим, что в начале мы имеем Xі = X и У = Y. Так как в каждый момент Природа может покрыть лишь конечное число ребер, множества Х\Х и Y\Y всегда конечны и имеют равную мощность. Элементы Х\Х и Y \ Y называются свободными вершинами.

Второе инвариантное свойство использует понятие ранга. Определим ранг вершины как разницу между числом исходящих из этой вершины покрытых слева и покрытых справа (ненаправленных) ребер. Ранг определен для вершин как из X, так и из У; легко видеть, что ранг гапк(ж) вершины х Є X не превосходит 2П (так как число исходящих направленных ребер не превосходит 2П) и что гапк(у) — 2п для у Є Y (по той же причине). Теперь мы готовы сформулировать второе свойство: (12) Концы любого непокрытого ребра имеют равные ранги. Более того, (13) для каждого к число свободных левосторонних вершин ранга к равно числу свободных правосторонних вершин ранга к. Условия (12) и (13) влекут, что общее число вершин, имеющих ранг к одинаково для X и Y. Перед описанием стратегии посмотрим, что происходит когда Природа покрывает какое-то ненаправленное ребро (х,у), не покрытое до сих пор. (Если это ребро было покрыто в противоположном направлении, ход Природы ничего по-существу не изменит.) Обе конечные вершины х и у меняют ранг одинаково (он увеличивается или уменьшается на 1) и продолжают иметь равные ранги. Концы ребра становятся свободными вершинами. Так как они имеют равный ранг, условие (13) остается верным. Теперь опишем стратегию. Если Природа на своем ходе не создала ни одного ребра (или покрыла ребро, уже бывшее покрытым в противоположном направлении), то Математик не делает ничего. Предположим, что Природа покрыла до сих пор не покрытое ребро (х,у). Тогда Математик ищет свободную вершину у имеющую тот же ранг, что и у после хода Природы, не соединенную с х ненаправленным ребром. Если такая вершина у существует, Математик создает ненаправленное ребро (х,у ). Так как х и у имеют равные ранги, условия (12) и (13) остаются верными и после хода Математика. Если же не нашлось у , обладающей указанными свойствами, Математик отмечает х. Почему эта стратегия выигрывает? Напомним, что rank(z) 2П для всех хбіи тапк(у) —2П для всех у Є У. Таким образом, (12) и (13) Глава 3. СИСТЕМЫ СЛОВ С БОЛЬШОЙ ВЗАИМНОЙ СЛОЖНОСТЬЮ 47 означают, что все ранги заключены между —2П и 2П. Значит, число входящих направленных ребер (для любой вершины) ограничено числом 2-2п и для любой вершины х общее число исходящих покрытых ненаправленных ребер не превышает 2П + 2 2П = 3 2П (2П для исходящих и 2-2" для входящих направленных ребер). Докажем, что для любого к число свободных вершин ранга & в У (а значит и в X) не превосходит 3 2П: если оно достигает 3-2", то дальше увеличиться не может. Действительно, если новая свободная вершина у Є У ранга к появилась после того, как Природа покрыла ребро (х, у), то Математик может найти у на следующем ходе, так как не более 3 2П вершин ранга к может быть соединено с х ненаправленным ребром и есть 3 2П + 1 свободных вершин ранга к в Y (включая у). Таким образом, общее число свободных вершин ограничено числом так как есть не более 2 2n + 1 возможных значений ранга и не более 3 2П свободных вершин каждого ранга. То есть, не более 22п+4 вершин окажется отмечено (отмеченные вершины остаются свободными навсегда) и условие (4) выполнено. Также легко увидеть, что выполнено условие (3): если некоторая вершина х Є X так и не была отмечена, то появится ненаправленное ребро (х,у), которое так и останется непокрытым (потому, что ребро, однажды покрытое не может появится снова, а общее число ребер, исходящих из х ограничено). Лемма 3.1 доказана. Замечание 1. Доказательство становится немного проще если определить гапк(г ) как пару: число покрытых слева исходящих ребер и число покрытых справа исходящих ребер. Однако такой подход несколько ослабляет утверждение теоремы. Он работает лишь если К(х) 2,п + с вместо К{х) 2n + с. Теорема 3.3. Для любых натуральных чисел типи любого двоичного слова хо такого, что K{XQ) п(т2 + т + 1) + 5 logm + 0(1) выполнено следующее: существуют слова xi,...,xm такие, что п K(XI\XJ) n + 5logm + 0(1) при 0 г, j т, і ф j.

Вероятностный подход

Пусть даны два двоичных слова х и у. Будем рассматривать всевозможные программы р, для которых р(х) = у (на входе х программа р дает результат у). Какова минимальная возможная длина такой программы? При разумном выборе языка программирования она близка к К(у х) (условной колмогоровской сложности слова у при известном х). В данной главе мы будем рассматривать сложность с логарифмической точностью, пренебрегая членами порядка O(logn), где п максимальная длина рассматриваемых слов, и с этой точностью разные варианты сложности совпадают. Поэтому результаты этой главы остаются верными для различных вариантов определения колмогоровской сложности (обычная, префиксная и др.), так как все они отличаются друг от друга не более чем на логарифмическое слагаемое.

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

Будем рассматривать (для данных х и у) все такие описания, то есть все слова р, для которых К (у \ х,р) РИ 0. Легко проверить, что любое из них имеет длину и сложность не меньше К (у ж), и что эта оценка достигается (оба утверждения понимаются с точностью до O(logn), при этом та же точность требуется в приближенном равенстве К (у х,р) « 0 при определении описания).

Будем говорить, что описание р является упрощением описания р, если К(р р) 0 (с логарифмической точностью). Это отношение можно считать (с естественными оговорками о точности) частичным порядком, и представляет интерес структура множества всех кодов (для данных х, у) относительно этого порядка.

Среди описаний имеется, естественно, и само слово у. Как доказано в [9] (Теорема 1.6 из раздела 1.4 настоящей работы), существует описание минимальной длины, являющееся упрощением у (т.е. простое при известном у). Мы покажем, что для произвольного описания это уже не так: может существовать описание р, имеющее сложность много больше К (у х), но не имеющее упрощений существенно меньшей сложности. Сформулируем это более точно: Теорема 4.1. Существуют такие константы с\ С2 с$, а такоісе с и є О, что для всякого натурального п найдутся слова х,у,р со следующими свойствами: (a) К(у х,р) clogn ( слово р является описанием у при известном х с логарифмической точностью); (b) К(у х) с\п (сложность у при известном х мала...); (c) К(р) сзп (.. .по сравнению со слоэюностъю р); (а1) не существует слова р , для которого К(р ) С2П, К(р р) еп и К (у х,р ) еп (... по не существует описания р , упрощающего р до промеоісуточной слоэюпости счп). Заметим, что мы используем более либеральные линейные ограничения на К(р р) и К(у х,р ) по сравнению с первоначально предполагавшимся O(logn), но даже для таких границ слова р может не быть. В следующих разделах мы изложим два различных доказательства этого утверждения, имея в виду проиллюстрировать два различных метода построения объектов с заданными сложностными характеристиками: игровой и вероятностный. 4.1 Игровой подход Рассмотрим следующую игру с полной информацией, в которой мы играем с противником. Пусть даны конечные множества Р, Р , X и Y (как мы увидим, они будут соответствовать словам р,р ,х,у). Игроки ходят по очереди. Мы строим частичную функцию : РхХ — Y. Изначально эта функция нигде не определена; на каждом ходу мы можем доопределить ее в некоторых точках (но имеем право и не менять ее); уже имеющиеся значения мы изменить не можем. Противник строит две многозначные функции (р: Р — Р иф: Р хХ —У Y. (Другими словами, значениями (р являются конечные подмножества множества Р , а значениями ф - конечные подмножества Y.) Изначально функции (риф нигде не определены (другими словами, все их значения пусты); на каждом ходу противник имеет право доопределять их произвольным образом (добавляя новые значения в уже определенных точках или в тех, где значений еще не было); он может также и не менять (риф, но не может изъять ранее добавленные значения. При этом он обязан соблюдать следующие ограничения: функция р на любом аргументе принимает не более а значений, а функция ф - не более /3 значений. Ясно, что каждый игрок может сделать лишь конечное число ходов (на которых он что-то меняет), поэтому с некоторого момента функции стабилизируются. Победа присуждается по таким правилам: мы выиграли, если существуют такие рЄР, хЄХиуЄУ, для которых (р, х) = у и которые не покрыты противником: это означает, что не существует р Є (р(р), для которого у Є ф(р ,х). Таким образом, игра полностью задается множествами X, У, Р и Р (фактически важны лишь их мощности), а также параметрами а и /3. Имеет место простое наблюдение: Лемма 4.1. Если а то мы можем гарантировать выигрыш в описанной игре. Доказательство. В самом деле, первое условие гарантирует нам, что если есть пара р, х, на которой функция еще не определена, то можно так выбрать значение у = (р,х), чтобы оно не было покрыто (на данный момент игры). (Для каждого из не более чем а значений р Є р(х) имеется не более чем (3 значений у Є ф(р ,х), и можно выбрать (р, х) отличным от всех этих значений.) Действуя таким образом, мы на каждый (нетривиальный) ход противника отвечаем не более чем одним своим, и второе условие гарантирует, что мы не заполним таблицу преждевременно (число возможных ходов противника меньше, чем у нас). В самом деле, для каждого из \Р\ ар- гументов значение функции р может пополняться не более а раз, и для каждой из \Х\ \Р \ пар (р ,х) значение функции ф может пополняться не более fi раз. Попытаемся теперь применить эту лемму для доказательства интересующего нас утверждения. Фиксируем (достаточно большие) константы с\ С2 сз, а также є 0 (малое по сравнению с с\ и разностями сі — с\ и Сз — Сг). В качестве Y возьмем множество всех слов длины не больше сіп, в качестве Р - множество всех слов длины не больше С2П, в качестве Р - множество всех слов длины не более сзп. Множество X можно выбирать по-разному (это связано с тем, что на сложность х у нас нет никаких ограничений); например, можно положить X = Y.

Предположим, что противник постепенно включает в ip(p) все слова р (указанных выше длин), для которых К(р \ р) єп, а в тр(р , х) - все слова у (соответствующих длин), для которых К(у х,р ) en. Это можно делать алгоритмически, поскольку функция К перечислима сверху и все слова малой сложности рано или поздно обнаружатся. Такое поведение будет законно при a = /3 = 2ЄП. Легко проверить, что условия леммы выполнены (с запасом):

Похожие диссертации на Наборы конечных объектов с заданными информационными соотношениями между ними

Соотношение дискретных и непрерывных алгоритмов управления линейными объектами Шарыгин Иван Николаевич

Помехоустойчивые интерферометрические системы контроля объектов на основе формирования, регистрации и обработки набора интерференционных картинМаргарянц, Никита Борисович

Соотношение подлежащего и дополнения с семантическими категориями субъекта и объектаИосилевич Наталья Вячеславовна

Метод и программно-техническое обеспечение контроля соотношения процессов возбуждения и торможения человека на основе измерения времени реакции на движущийся объектПесошин Андрей Валерьевич