Некоторые версии дискретной ККМ-леммы и их вычислительная сложность

Александр Гришутин

Некоторые версии дискретной ККМ-леммы и их вычислительная сложность

В этой работе мы сформулируем и решим задачу, находящуюся на пересечение двух больших областей науки $~-$ теории неподвижных точек и теории сложности вычислений. Теория неподвижных точек изучает теоремы, которые гарантируют наличие неподвижных точек (это понятие определяется по-разному в зависимости от теоремы). Классическим результатом в этой области является теорема Брауэра о неподвижной точке \cite{brower}, которая гласит, что у любого непрерывного отображения шара самого в себя найдётся неподвижная точка. Многие задачи этой теории имеют соответствующие вычислительные задачи, которые лежат и полны в сложностном классе \textbf{PPAD}, введённом Пападимитриу в \cite{papadimitrou}.

Математика

Дипломы

Вуз: Московский физико-технический институт (государственный университет) (МФТИ)

ID: 5f384560cd3d3e0001ba5211

UUID: c5e4ee00-c163-0138-1aed-0242ac180006

Язык: Русский

Опубликовано: больше 4 лет назад

Просмотры: 13

10.36

Александр Гришутин

Московский физико-технический институт (государственный университет) (МФТИ)

Комментировать 10

Рецензировать 0

Скачать - 2,1 МБ

Поделиться работой

СОДЕРЖАНИЕ СОДЕРЖАНИЕ Содержание Аннотация 2 1 Введение 1.1 Используемые определения . . . . . . . . . . . . . . . . . . 1.2 Известные результаты . . . . . . . . . . . . . . . . . . . . . 1.3 ККМ-лемма . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 4 6 2 Дискретная постановка ККМ-леммы 7 3 Двумерная дискретная KKM-лемма 10 3.1 Случай треугольной сетки . . . . . . . . . . . . . . . . . . . 10 3.2 Случай квадратной сетки . . . . . . . . . . . . . . . . . . . 14 4 Трёхмерная дискретная KKM-лемма 18 4.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Формулировка и доказательство теоремы . . . . . . . . . . 19 5 Полнота в PPAD 23 5.1 Сведение 2D-KKM к 2D-SPERNER . . . . . . . . . . . . . . 23 5.2 Сведение 2D-SPERNER к 2D-KKM . . . . . . . . . . . . . . 23 5.3 DISCRETE-KKM лежит в PPAD . . . . . . . . . . . . . . 26 6 Заключение 28 Cписок литературы 29 1

СОДЕРЖАНИЕ СОДЕРЖАНИЕ Аннотация Для класса задач поиска PPAD уже доказана полнота многих важных теорем о неподвижной точке из разных областей математики, таких как теорема Брауэра о неподвижной точке, Лемма Шпернера, поиск равновесия Нэша, теорема Какутани, поиск клиринговых платежей в финансовых сетях с кредитными дефолтными свопами, теорема Жордана и другие. Однако до сих пор не была доказана полнота ККМ-леммы, другой не менее известной теоремы о неподвижной точке. В этой работе мы восполняем этот пробел, формулируя и доказывая соответствующую дискретную задачу, а впоследствии доказываем полноту двумерной дискретной ККМ-леммы в классе PPAD, а также доказываем принадлежность более общей задачи DISCRETE-KKM тому же классу. 2

1 1 ВВЕДЕНИЕ Введение В этой работе мы сформулируем и решим задачу, находящуюся на пересечение двух больших областей науки ´ теории неподвижных точек и теории сложности вычислений. Теория неподвижных точек изучает теоремы, которые гарантируют наличие неподвижных точек (это понятие определяется по-разному в зависимости от теоремы). Классическим результатом в этой области является теорема Брауэра о неподвижной точке [1], которая гласит, что у любого непрерывного отображения шара самого в себя найдётся неподвижная точка. Многие задачи этой теории имеют соответствующие вычислительные задачи, которые лежат и полны в сложностном классе PPAD, введённом Пападимитриу в [5]. 1.1 Используемые определения Напомним необходимые определения из теории сложности вычислений. Определение 1. Класс NP Классом NP (Non-deterministic Polynomial) называется множество языков 𝐴, для которых существует функция 𝑉 p𝑥, 𝑠q, принимающая значения 0{1, вычислимая за полиномиальная от длины 𝑥 входа такая, что ∙ Если 𝑥 P 𝐴, то D𝑠 𝑉 p𝑥, 𝑠q “ 1; ∙ Если 𝑥 R 𝐴, то @𝑠 𝑉 p𝑥, 𝑠q “ 0; Определение 2. Задача поиска Пусть задан полиномиально вычислимый предикат 𝑉 p𝑥, 𝑦q. Задачей поиска называется задача отыскания по входу 𝑥 такого 𝑦, что 𝑉 p𝑥, 𝑦q “ 1, либо указания, что таких 𝑦 не существует. Определение 3. Класс TFNP Классом TFNP (Total Functional Non-deterministic Polynomial) называется класс задач поиска, таких что для любого 𝑥 существует 𝑦, такой что 𝑉 p𝑥, 𝑦q “ 1 и 𝑉 p𝑥, 𝑦q тоже полиномиально вычислимым. Определение 4. Класс PPAD Пусть даны два полиномиальных алгоритма 𝑆 (successor) и 𝑃 (predecessor), 3

1.2 Известные результаты 1 ВВЕДЕНИЕ получающие на вход строку из t0, 1u𝑛 и выдающие также строку из t0, 1u𝑛 . Эти алгоритмы задают неявный орграф, в котором есть ребро p𝑥, 𝑦q ðñ 𝑦 “ 𝑆p𝑥q ^ 𝑥 “ 𝑃 p𝑦q. В задаваемом таким образом графе входящие и исходящие степени всех вершин не превосходят 1, а значит все его компоненты ´ либо цепочки, либо циклы. Классом PPAD называется класс задач поиска, в которых в орграфе, заданным таким образом, по данному источнику 𝑥 (то есть 𝑆p𝑃 p𝑥qq ‰ 𝑥, 𝑃 p𝑆p𝑥qq “ 𝑥 и 𝑆p𝑥q ‰ 𝑥) необходимо найти либо сток (то есть 𝑃 p𝑆p𝑥qq ‰ 𝑥, 𝑃 p𝑥q ‰ 𝑥, 𝑆p𝑃 p𝑥qq “ 𝑥), либо другой источник. Существование стока или другого источника в таком графе легко доказывается, например, индукцией по числу вершин в графе. Замечание. Задача из определения PPAD называется 𝐸𝑁 𝐷-𝑂𝐹 -𝑇 𝐻𝐸𝐿𝐼𝑁 𝐸. Замечание. Из определений ясно, что PPAD Ă TFNP Ă NP. 1.2 Известные результаты Приведём список теорем и задач, чья полнота в классе PPAD уже доказана. 1. Лемма Шпернера ([2]). В [5] поставлена вычислительная задача и доказана полнота трёхмерного случая в классе PPAD, а в [18] доказана полнота двумерного случая. 2. Теорема о причёсывании ежа о том, что любое ненулевое непрерывное векторное поле 𝑓 на сфере имеет точку 𝑥, в котором 𝑓 p𝑥q перпендикулярно сфере. См. [15]. 3. Теорема Брауэра о неподвижной точке о том, что любое непрерывное отображение замкнутого шара само в себя в конечномерном пространстве имеет неподвижную точку. См. [10]. 4. Равновесие Нэша о сложности поиска равновесного набора смешанных стратегий в играх без коалиций. В [8] доказана полнота для случая 4 игроков, в [7] доказана полнота для случая 3 игроков и, наконец, в [9] доказана полнота для случая 2 игроков (задача BIMATRIX). 4

1.2 Известные результаты 1 ВВЕДЕНИЕ 5. Теорема Жордана о том, что простая плоская замкнутая кривая разбивает R2 на 2 связные компоненты и является их общей границей. В [13] ставится соответствующая вычислительная задача ZEROSURFACE-CROSSING и доказывается её полнота в PPAD. 6. Лемма Такера. Соответствующая вычислительная задача поставлена и доказана в [11]. 7. Теорема Борсука-Улама. Доказательство полноты в PPAD см. [5]. 8. Клиринговые платежи в финансовых сетях с кредитным дефолтным свопом, см. [14]. Отдельно уделим внимание теореме 2D-SPERNER и соответствующей вычислительной задаче, так как они нам пригодятся в дальнейшем в этой работе. Начнём со следующего определения: Определение 5. Двумерная шпернеровская раскраска на квадрате Пусть дана квадратная сетка 𝐾 ˆ 𝐾 и её раскраска в 3 цвета t0, 1, 2u, на которую накладываются следующие правила: 1. Каждый квадратик покрашен ровно в 1 цвет. 2. Левый нижний квадратик покрашен в цвет 0, правый нижний квадратик покрашен в цвет 1, левый верхний — в цвет 2. 3. Квадратики на нижней стороне покрашены в цвета 0 или 1, на левой стороне в цвета 0 или 2, на правой и верхней стороне — в цвета 1 и 2. Теорема 1. Двумерная лемма Шпернера на квадрате Пусть дана квадратная сетка 𝐾 ˆ 𝐾 и её раскраска в 3 цвета t0, 1, 2u, являющаяся шпернеровской. Тогда найдётся узел сетки, среди соседей которого есть квадраты всех трёх цветов. Определение. Задача 2D-SPERNER Пусть дана квадратная сетка 𝐾 ˆ 𝐾 и её раскраска в 3 цвета t0, 1, 2u 5

1.3 ККМ-лемма 1 ВВЕДЕНИЕ задана с помощью схемы полиномиального размера 𝐶. Будем интерпретировать выход 𝐶 как раскраску в один из трёх цветов, взяв остаток от выхода схемы по модулю 3. Задачей 2D-SPERNER будем называть задачу поиска по 𝐶 узла сетки, среди соседей которого встречаются все три цвета либо поиск места, в котором нарушается условие шпернеровской раскраски. 1.3 ККМ-лемма Наша работа будет посвящена результату, полученным Кнастером, Куратовским и Мазуркевичем в 1929 году в [3]. Теорема. ККМ-лемма Пусть Δ𝑛´1 ´ p𝑛 ´ 1q-мерный симплекс с 𝑛 вершинами 1, . . . , 𝑛. ККМпокрытием называется набор 𝐶1 , . . . , 𝐶𝑛 замкнутых множеств таких, что: @𝐼 Ă t1, . . . , 𝑛u выпуклая оболочка вершин, соответствующих 𝐼, Ť покрыта объединением соответствующих множеств 𝑖P𝐼 𝐶𝑖 . Ş Тогда 𝑛𝑖“1 𝐶𝑖 ‰ H. Доказательство. Эта теорема имеет несколько разных доказательств. Автор данной работы находит наиболее простым и элегантным доказательство с помощью леммы Шпернера (напр. [17]). Цель данной работы: сформулировать дискретную задачу-аналог ККМлеммы, поставить соответствующую вычислительную задачу и доказать её принадлежность классу PPAD. 6

2 2 ДИСКРЕТНАЯ ПОСТАНОВКА ККМ-ЛЕММЫ Дискретная постановка ККМ-леммы Чтобы сформулировать дискретную версию ККМ-леммы, первым делом надо определить, что мы будем рассматривать в качестве аналога замкнутых множеств на дискретной сетке. Поскольку речь идёт о раскрасках, достаточно наложить какие-то условия на то, как могут пересекаться ячейки сетки, покрашенные в разные наборы цветов. Начнём с треугольной сетки, как наиболее близкой к исходной постановке ККМ-леммы. Вообще, формулировка понятия непрерывное множество на дискретной сетке довольно неочевидная вещь. Можно было бы потребовать, чтобы все граничные объекты множества, то есть те, у которых есть сосед, принадлежащий другому множеству, были обязаны принадлежать какому-то другому множеству (пример соответствующей теоремы можно найти в [16]). Однако подобная формулировка не обобщается на пространства произвольной размерности, поэтому в этой работе мы будем накладывать следующее требование (обоснование такого выбора можно также найти в [16]): Определение 6. Дискретное ККМ-условие на цвета Если две ячейки сетки 𝑎 и 𝑏 считаются соседями, то E𝑖, 𝑗 P C : 𝑖 P 𝐶p𝑎q ^ 𝑗 R 𝐶p𝑎q ^ 𝑖 R 𝐶p𝑏q ^ 𝑗 P 𝐶p𝑏q, где C ´ множество всех цветов (разное для разных постановок задачи), а 𝐶p𝑥q ´ набор цветов, в которые покрашена ячейка 𝑥. Сразу заметим, что Определение 6 равносильно следующему: Определение 7. Критерий дискретного ККМ-условия на цвета Если две ячейки сетки 𝑎 и 𝑏 считаются соседями, то либо 𝐶p𝑎q “ 𝐶p𝑏q, либо 𝐶p𝑎q Ă 𝐶p𝑏q, либо 𝐶p𝑏q Ă 𝐶p𝑎q. Замечание. Этот критерий удобнее использовать при проверке контрпримеров, которые будут ниже в работе. Сформулируем и докажем лемму, которая в дальнейшем поможет в доказательстве теорем в этой работе: 7

2 ДИСКРЕТНАЯ ПОСТАНОВКА ККМ-ЛЕММЫ Лемма 1. Достаточное условие существования всецветной вершины в клике. Пусть дана клика 𝐾𝑛 , где 𝑛 ě 1, каждая вершина которой покрашена в некоторое подмножество цветов из t0, 1, . . . , 𝑐 ´ 1u по следующим правилам: 1. Для каждого цвета из t0, 1, . . . , 𝑐 ´ 1u найдётся хотя бы одна вершина, покрашенная в этот цвет. 2. Любая пара вершин, соединённая ребром, удовлетворяет дискретному ККМ-условию на цвета (Определение 6). Тогда найдётся вершина, покрашенная во все цвета. Доказательство. Докажем лемму индукцией по 𝑐. ∙ База индукции. 𝑐 “ 1. В этом случае утверждение леммы следует из условия 1. ∙ Переход. Пусть лемма доказана для любого числа цветов из 1, . . . , 𝑐´ 1. Докажем для 𝑐 цветов. Пусть 𝐴𝑐´1 ´ множество вершин 𝐾𝑛 , покрашенных в цвет 𝑐´1. Если мы докажем, что для любого цвета 𝑖 P t0, 1, . . . , 𝑐 ´ 2u найдётся вершина 𝑥 P 𝐴𝑐´1 , такая что 𝑥 покрашен в цвет 𝑖, то к 𝐴𝑐´1 , поскольку оно непусто по условию 1, можно будет применить предположение индукции, и найдётся вершина 𝑣 P 𝐴𝑐´1 , покрашенная во все цвета до 𝑐 ´ 2. Но она будет также покрашена в цвет 𝑐 ´ 1 по построению 𝐴𝑐´1 и, следовательно, будет той вершиной, которую мы ищем. Предположим, что нашёлся такой цвет 𝑖 P t0, . . . , 𝑐 ´ 2u, что ни одна вершина 𝐴𝑐´1 не покрашена в цвет 𝑖. Тогда, по условию 1, среди вершин 𝑉 p𝐾𝑛 qz𝑉 p𝐴𝑐´1 q найдётся вершина 𝑦, покрашенная в цвет 𝑖. Выберем теперь произвольную вершину 𝑥 из 𝐴𝑐´1 и посмотрим на пару вершин 𝑥, 𝑦: 𝑥 покрашена в цвет 𝑐 ´ 1, но не покрашена в цвет 𝑖, а 𝑦 покрашена в цвет 𝑖, но не покрашена в цвет 𝑐 ´ 1. Значит, мы нашли противоречие с условием 2 и наше предположение неверно. Следовательно к 𝐴𝑐´1 можно применить предположение индукции и найти интересующую нас вершину, покрашенную во все цвета. 8

2 ДИСКРЕТНАЯ ПОСТАНОВКА ККМ-ЛЕММЫ В контексте этой работы графы будут строиться так: вершинами графа мы будем считать объекты сетки (треугольники, квадраты, кубы), а рёбрами будем соединять те объекты, которые мы будем считать соседями. 9

3 3 ДВУМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА Двумерная дискретная KKM-лемма В этой главе мы сформулируем и докажем две версии дискретной ККМлеммы на плоскости. 3.1 Случай треугольной сетки Сформулируем предположение о том, как могла бы быть устроена ККМлемма в случае треугольной сетки. Треугольную сетку мы выбрали как наиболее близкую к исходной постановке ККМ-леммы. Гипотеза 1. Пусть 𝐴0 𝐴1 𝐴2 ´ правильный треугольник на плоскости, триангулированный стандартным образом, то есть каждая сторона поделена на 𝑘 равных частей (см. рис 3.1) и эти точки соединены всевозможными линиями, параллельными сторонам треугольника. Пусть каждый треугольник покрашен в некоторый набор из 3 цветов. Для простоты, будем считать, что цвета ´ это числа: C “ t0, 1, 2u и каждый треугольник покрашен в некоторое подмножество C, причём выполняются следующие условия: 1. Каждый треугольник покрашен хотя бы в один цвет (то есть подмножество не может быть пустым). 2. Треугольник при вершине 𝐴𝑖 покрашен в цвет 𝑖 и, возможно, другие цвета. 3. Все треугольники, касающиеся стороны 𝐴𝑖 𝐴𝑗 , покрашены хотя бы в один из цветов 𝑖 и 𝑗 (и, возможно, в оставшийся цвет) 4. Для любых двух соседних по ребру треугольников выполняется дискретное ККМ-условие на цвета (Условие 6). Тогда найдётся треугольничек, покрашенный во все три цвета одновременно. 10

3.1 Случай треугольной сетки 3 ДВУМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА 𝐴0 𝐴1 𝐴2 Рис. 3.1: Стандартная триангуляция Факт. Оказывается, что в такой постановке гипотеза неверна! Приведём контрпример (см. рис 3.2): 𝐴0 𝐴1 𝐴2 Рис. 3.2: Контрпример в случае, если соседями считаются треугольники с общим ребром Раз в таких условиях наша гипотеза оказалась неверна, попробуем усилить условия, увеличив множество пар треугольников, которые мы считаем соседями. Вариантов у нас немного: теперь соседями мы будем считать треугольники, имеющие хотя бы одну общую точку. 11

3.1 Случай треугольной сетки 3 ДВУМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА В таких условиях уже можно сформулировать и доказать следующую теорему: Теорема 2. Дискретная ККМ-лемма на треугольнике Пусть выполняются условия Гипотезы 1 за исключением того, что соседними считаются треугольники, имеющие хотя бы одну общую точку. Тогда найдётся треугольник сетки, покрашенный во все 3 цвета одновременно. Доказательство. Покрасим все точки треугольника по непрерывности: каждое ребро покрасим в цвета всех смежных с ним треугольников, аналогично поступим с вершинами. Заметим теперь, что мы получили раскраску, удовлетворяющую условиям ККМ-леммы в непрерывной постановке. Действительно ∙ Множество точек, покрашенных в каждый цвет замкнуто, так как является объединением конечного множества замкнутых множеств ∙ Каждый угол покрашен в соответствующий цвет, так как в этот цвет покрашен соответствующий угловой треугольничек. ∙ Каждая грань покрыта объединением соответствующих цветов, поскольку составляющую эту грань отрезки сетки принадлежат треугольникам, которые мы красили ровно необходимым образом. . Следовательно, существует точка 𝑋 внутри 𝐴𝐵𝐶, покрашенная во все 3 цвета. Рассмотрим случаи того, куда могла попасть 𝑋: Случай 1. 𝑋 лежит строго внутри какого-то треугольника сетки. Тогда весь этот треугольник покрашен во все цвета и теорема доказана. Случай 2. 𝑋 попала на ребро сетки (см. рис 3.3). Пусть треугольники, содержащие ребро, на которое попала 𝑋 — в треугольниках 𝑃 𝑄𝑅 и 𝑃 1 𝑄𝑅. Заметим, что тогда эти треугольники образуют клику размера 2 в смысле леммы 1. Действительно, в каждый цвет покрашен хотя бы один и з треугольников, для любой пары вершин 12

3.1 Случай треугольной сетки 3 ДВУМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА выполняется дискретное ККМ-условие на цвета. Из леммы следует, что один из треугольников покрашен во все три цвета и теорема в этом случае доказана. Внимательный читатель может заметить, что в этом случае достаточно даже слабого дискретного ККМ-условия. P X Q R P’ Рис. 3.3: Случай точки на ребре Случай 3. 𝑋 попала в вершину сетки (см. рис. 3.4). Опять-таки заметим, что треугольники 𝑃 𝑄𝑋, 𝑄𝑅𝑋, 𝑅𝑆𝑋, 𝑆𝑇 𝑋, 𝑇 𝑊 𝑋, 𝑊 𝑃 𝑋 образуют клику размера 6 в смысле сильного дискретного ККМусловия, так как пересекаются по вершине 𝑋. Значит, по всё той же лемме 1 найдётся треугольник, покрашенный во все три цвета и теорема доказана. Q P X U R S T Рис. 3.4: Случай точки в вершине сетки 13

3.2 3.2 Случай квадратной сетки 3 ДВУМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА Случай квадратной сетки Треугольная сетка обладает двумя важными недостатками: у неё нет простых обобщений уже на пространства размерности 3 и её неудобно кодировать. Поэтому мы переформулируем нашу теорему на случай квадратной сетки, а затем обобщим на большие размерности. Замечание. При формулировании следующей и дальнейших теорем, связанных с квадратной/кубической сеткой, говоря, что квадрат/куб имеет координаты p𝑥, 𝑦, 𝑧q мы будем иметь в виду, что такие координаты имеет его вершина с минимальными координатами (в двумерном случае это левый нижний угол). Теорема 3. Дискретная ККМ-лемма на квадрате Пусть дан квадрат 𝐴𝐵𝐶𝐷, на котором задана сетка 𝐾 ˆ 𝐾, разбивающая его на 𝐾 2 квадратиков. Пусть каждый квадрат покрашен в один из 3 цветов со следующими условиями (см. рис 3.5): 1. Квадрат p0, 0q покрашен в цвет 0 (и, возможно, другие цвета). 2. Все квадраты (кроме p0, 0q), у которых 𝑖-я координата (номер строки или столбца) равна 0, не покрашены в цвет 𝑖. 3. Все квадраты, у которых хотя бы одна из координат равна 𝐾 ´ 1, не покрашены в цвет 0. Другими словами, квадратики вдоль верхней и правой грани можно красить только в цвета 1 и 2. 4. Для любых двух квадратиков, соседних по вершине, выполняется дискретное ККМ-условие на цвета. Тогда найдётся квадратик, который покрашен во все 3 цвета. 14

3.2 Случай квадратной сетки 3 ДВУМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА B C 2 0 S S 0 S S 0 S S 0 S S 0 S S 0 S S 0 S S 0/2 S S 0/2 S S 0/2 S S 0/2 S S 0/2 S S 0/2 S S 0 0 0 0 0 0 0 0/1 0/1 0/1 0/1 0/1 0/1 1 D A Рис. 3.5: Условия на раскраску квадратов сетки Доказательство. Пусть дана ККМ-раскраска в цвета t0, 1, 2u. Перекрасим клетки в цвета t0, 1, 2u по следующему правилу (пример см. на рис. 3.6): ∙ t0, 01, 02, 012u Ñ 0. ∙ t1, 12u Ñ 1. ∙ t2u Ñ 2. Заметим, что теперь мы получили раскраску квадратной сетки удовлетворяющую условиям 2D-SPERNER (Теорема 1). Действительно, ∙ В исходной раскраске квадрат p0, 0q мог иметь один из следующих цветов:t0, 01, 02, 012u и в новой раскраске всем этим вариантам соответствует цвет 01 . 15

3.2 Случай квадратной сетки 3 ДВУМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА (a) Пример 2D-KKM-раскраски (b) Построенная по этой раскраске 2D-SPERNERраскраска Рис. 3.6: Сведение 2D-KKM к 2D-SPERNER 16

3.2 Случай квадратной сетки 3 ДВУМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА ∙ Квадрат с координатами p0, 𝐾 ´ 1q мог быть покрашен только в цвет 1, и в новой раскраске это цвет 11 . С p𝐾 ´ 1, 0q ситуация симметричная. ∙ Квадраты вдоль нижней стороны (кроме угловых клеток) могли быть покрашены в следующие цвета 0, 01, 02, 012, loomo 1 on, а значит в новой loooooomoooooon 11 1 01 раскраске нижняя сторона покрашена в цвета 0 и 11 . С левой стороной симметрично. ∙ Квадраты вдоль правой и верхней сторон (кроме p0, 𝐾 ´ 1q и p𝐾 ´ 1, 0q) могли быть покрашены в цвета lo1, 12on, loomo 2 on, а значит в новой omo 11 21 раскраске верхняя и правая грани покрашены в цвета 1, 2. Значит найдётся узел сетки 𝑋, среди соседей которого найдутся клетки всех цветов из t01 , 11 , 21 u, пусть это клетки 𝐶01 , 𝐶11 , 𝐶21 соответственно. Докажем, что 𝐶01 в исходной раскраске был имел цвета 012. Действительно, мы строили нашу раскраску так, что цвет 𝑖1 в исходной раскраске обязательно содержит цвет 𝑖. Значит, четыре квадратика, содержащие 𝑋 образуют клику в смысле Леммы 1 (т.к. в постановке теоремы мы заявили, что считаем соседями квадратики, имеющие хотя бы одну общую вершину), а значит среди них в исходной раскраске найдётся квадратик, покрашенный во все три цвета. 17

4 4 ТРЁХМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА Трёхмерная дискретная KKM-лемма Этот раздел данной работы посвящён обобщению леммы на пространства больших размерностей. Мы сформулируем определение ККМ-раскраски в общем случае и проведём доказательство в трёхмерном случае, как наиболее удобном для визуализации. Доказательство же общего случая от доказательства трёхмерного случая практически ничем не будет отличаться. 4.1 Постановка задачи Пусть дан куб в пространстве R𝑛 , разделённый на 𝐾 𝑛 кубиков (то есть все кубики имеют вид p𝑥0 , 𝑥0 ` 1q ˆ p𝑥1 , 𝑥1 ` 1q ˆ . . . ˆ p𝑥𝑛´1 , 𝑥𝑛´1 ` 1q, где все 𝑥𝑖 P t0, 1, . . . , 𝐾 ´ 1uq. Раскрасим эти кубики в 𝑛 ` 1 цвет по следующим правилам (см. рис 4.1): Определение 8. ККМ-раскраска трёхмерной кубической сетки 1. Каждый кубик покрашен хотя бы в один цвет. 2. Если у кубика 𝑖-я координата равна 0, то он не покрашен в цвет 𝑖. 3. Если у кубика хотя бы одна координата равна 𝐾 ´ 1, то он не покрашен в цвет 0. 4. Если два кубика являются соседями, то для них выполняется дискретное ККМ-условие на цвета. То, какие кубики мы считаем соседними, мы уточним позже. Рис. 4.1: Правила покраски в трёхмерном случае 18

4.2 Формулировка и доказательство теоремы 4 ТРЁХМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА Вопрос, на который нам хочется ответить: Какие кубики нам надо считать соседними, чтобы из этого следовало наличие кубика, покрашенного во все цвета? Аналогично случаю в R2 , мы будем считать соседями кубики, имеющие хотя бы одну общую вершину. 4.2 Формулировка и доказательство теоремы Сформулируем и докажем теорему, считая соседними кубики, имеющие хотя бы одну общую точку, заодно в ходе доказательства увидев, почему недостаточно считать соседями даже кубики имеющие общее ребро. Итак: Теорема 4. Дискретная ККМ-лемма на кубе в R𝑛 , 𝑛 ě 3. Пусть дана ККМ-раскраска, на которую дополнительно наложено сильное условие на цвета, а именно: 4. Для любых двух кубиков, пересекающихся хотя бы по вершине, верно, что они либо покрашены в один и тот же набор цветов, либо набор цветов одного является подмножеством набора цветов другого. Тогда найдётся кубик, покрашенный во все 𝑛 ` 1 цвет. Доказательство. Проведём доказательство в R3 , параллельно делая замечания, как рассуждения обобщить до пространства произвольной размерности. Первым шагом дополним по непрерывности нашу раскраску кубиков до раскраски рёбер, граней и вершин. Достроим к граням нашего куба с 𝑥𝑖 “ 𝐾 пирамиды внешним образом как показано на 4.2. Назовём вершины этих достроенных пирамид 𝑉𝑖 соответственно цветам, а 𝑂 ´ начало координат. Заметим, что раскраска получившейся фигуры (склеенные куб и три (𝑛 в общем случае) пирамиды) топологически эквивалентна раскраске тетраэдра в 4 цвета (𝑛-мерного симплекса в 𝑛 ` 1 цветов в общем случае), подходящей под условия ККМ-леммы. Действительно, вершины этого тетраэдра покрашены в соответствующие 19

4.2 Формулировка и доказательство теоремы 4 ТРЁХМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА Рис. 4.2: Достроенные пирамиды с нескольких ракурсов цвета, рёбра 𝑂𝑉𝑖 покрыты 𝐶0 Y 𝐶𝑖 , рёбра 𝑉𝑖 𝑉𝑗 покрыты 𝐶𝑖 Y 𝐶𝑗 , грани 𝑂𝑉𝑖 𝑉𝑗 покрыты 𝐶0 Y 𝐶𝑖 Y 𝐶𝑗 и оставшаяся грань, которой топологически эквивалентна «внешняя крышка» нашей фигуры, покрыта 𝐶1 Y 𝐶2 Y 𝐶3 . Значит, найдётся точка 𝑋 внутри полученной фигуры, покрашенная во все цвета. Поскольку достроенные пирамиды покрашены только в один цвет, то 𝑋 обязана попасть внутрь исходного куба. Переберём, куда может попасть точка 𝑋: Случай 1. 𝑋 попала строго внутрь кубика. В этом случае весь кубик покрашен во все 4 цвета и мы обрели то, что искали. Случай 2. 𝑋 попала на грань между двумя кубиками. Этот случай полностью аналогичен случаю с точкой на ребре в двумерном случае и эти кубики образуют клику, а дальше по Лемме 1 получаем наличие кубика, покрашенного во все цвета. Случай 3. 𝑋 попала на ребро между двумя кубиками. Заметим, что если спроецировать картинку вдоль этого ребра, то задача сведётся к двумерному случаю, когда 𝑋 попала в вершину сетки. Заметим, что в этом случае, если считать соседями только кубики, имеющие общую грань, то из этого не будет следовать, что один из кубиков, содержащих 𝑋, покрашен во все цвета. Контрпример к этому можно увидеть на рис. 4.3: 20

4.2 Формулировка и доказательство теоремы 4 ТРЁХМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА 𝐶1 X 𝐶2 Рис. 4.3: Контрпример в R3 (спроецированный вдоль ребра), соседями мы считаем кубики с общей гранью, 𝑋 попала на ребро. Если же считать соседями кубики, смежные по ребру, то кубики 𝐶1 и 𝐶2 станут соседями и контрпример развалится. Более того, 4 кубика, содержащие ребро, на которое попала 𝑋, образуют клику размера 4 (т.к. каждый сосед каждого), на которой задана раскраска вершин в 4 цвета, подходящая под условие Леммы 1, а значит найдётся вершина (кубик), покрашенный во все 4 цвета. Получается, что в случае с точкой на ребре достаточно наложить условие на цвета для кубиков с общим ребром, тогда найдётся кубик, покрашенный во все 4 цвета. Однако, остаётся ещё последний случай, где нам опять понадобится усилить требования. Случай 4. 𝑋 попала в вершину сетки. В этом случае оказывается, что если не считать соседями кубики, имеющие только одну общую точку, то необязательно найдётся кубик, содержащий 𝑋 и покрашенный во все цвета. Приведём контрпример (рис. 4.4): Рис. 4.4: Контрпример в случае, когда 𝑋 попала в вершину сетки; соседними считаем кубики с общим ребром 21

4.2 Формулировка и доказательство теоремы 4 ТРЁХМЕРНАЯ ДИСКРЕТНАЯ KKM-ЛЕММА На рис. 4.4 указаны цвета кубиков, содержащих 𝑋. Чтобы не рисовать трёхмерную картинку, мы обошлись указанием графа связности, а именно на картинке смежны те кубики, которые имеют общую точку (на картинке) или соединены ребром. На этом контрпримере смежны те квадратики, у которых соответствующие кубики пересекаются по грани или по ребру. Итак, как мы видим, для того, чтобы сделать вывод о наличии кубика 4 цветов недостаточно считать соседями кубики с общим ребром, надо потребовать, чтобы соседними считались кубики имеющие хотя бы одну общую вершину. Наконец, чтобы доказать, что найдётся кубик, покрашенный во все цвета, заметим, что кубики, содержащие 𝑋 образуют клику размера 8 с раскраской в 4 цвета, удовлетворяющей условию Леммы 1 а значит одна из вершин (читай, кубик), покрашена во все цвета. Итак, мы доказали, что куда бы ни попала точка 𝑋, найдётся кубик, покрашенный во все четыре цвета, а значит теорема доказана. В общем случае, разумеется, рассуждения абсолютное аналогичные, поскольку во всех случаях кубики, содержащие 𝑋, являются соседями друг с другом и, по Лемме 1 один из них должен быть покрашен во все цвета. 22

5 5 ПОЛНОТА В PPAD Полнота в PPAD В этом разделе данной работы мы сформулируем вычислительные задачи, соответствующие доказанным ранее теоремам и изучим их отношение к классу PPAD. В частности, мы докажем, что 2D-KKM полна в PPAD, а DISCRETE-KKM начиная с пространства размерности 3 лежит в PPAD. Определение. Задача 2D-KKM Пусть дана квадратная сетка 𝐾 ˆ 𝐾 и её раскраска в 3 цвета t0, 1, 2u задана с помощью схемы полиномиального размера 𝐶. Чтобы интерпретировать выход этой схемы, как раскраску клетки, будем брать это значение по модулю 8, а получившееся значение будем считать битовой маской, кодирующей раскраску клетки. Задачей 2D-KKM будем называть задачу поиска по 𝐶 либо квадратика сетки, покрашенного во все три цвета, либо места, где нарушаются правила ККМ-раскраски. Теорема 5. Задача 2D-KKM является PPAD-полной. Доказательство. Чтобы доказать теорему 5, мы докажем, что 2D-KKM сводится к 2D-SPERNER и обратно. В свою очередь из полноты 2DSPERNER, доказанной в [18], будет следовать полнота 2D-KKM, поскольку сведение 2D-KKM к 2D-SPERNER доказывает принадлежность 2D-KKM к PPAD, а сведение 2D-SPERNER к 2D-KKM доказывает полноту последней в PPAD. 5.1 Сведение 2D-KKM к 2D-SPERNER Данное сведение мы провели при доказательстве теоремы 3. 5.2 Сведение 2D-SPERNER к 2D-KKM Пусть дана раскраска из 2D-SPERNER. Построим в более мелкую сетку размера p2𝐾 `1qˆp2𝐾 `1q, клетки которой будут соответствовать клеткам, рёбрам и узлам исходной сетки. Клетки, соответствующие клеткам исходной сетки (назовём их C-клетки), покрасим в тот же цвет. Клетки, соответствующие рёбрам сетки (назовём их E-клетки), покрасим в цвета 23

5.2 Сведение 2D-SPERNER к 2D-KKM 5 ПОЛНОТА В PPAD клеток, которые они разделяли (получится одно- или двуцветная клетка). Клетки, соответствующие вершинам сетки (назовём их V-клетки) покрасим в цвета клеток, которые эту вершину содержат (получится одно-, дву- или трёхцветная клетка). Пример исходной раскраски и получившейся можно найти на рис. 5.1. (a) Пример 2D-SPERNER-раскраски (b) Построенная раскраска по этой раскраске 2D-KKM- Рис. 5.1: Сведение 2D-SPERNER к 2D-KKM Докажем, что получившаяся раскраска удовлетворяет граничным условиям ККМ-раскраски квадратной сетки (см. Теорему 3): 1. Левый нижний квадратик покрашен в цвет 0, поскольку он соответствует левому нижнему углу исходной сетки, а он принадлежит только одному квадратику, который как раз покрашен в цвет 0. 2. Квадратики на нижней стороне новой сетки могут быть либо Eклетками, либо V-клетками, а значит покрашены в цвета 0, 1 или 01, но не покрашены в цвет 2. Аналогично с квадратиками на левой стороне новой сетки. 3. Опять же аналогично предыдущему пункту, квадратики верхней и правой стороны покрашены в цвета 1, 2 или 12. 24

5.2 Сведение 2D-SPERNER к 2D-KKM 5 ПОЛНОТА В PPAD Проверим, что соседние квадратики новой сетки удовлетворяют дискретному ККМ-условию на цвета. Возможны следующие случаи типов соседних квадратиков: (a) C-E (b) E-V (c) C-V 𝐸2 𝐸1 (d) 𝐸1 и 𝐸2 не конфликтуют (e) E-E, конфликт Рис. 5.2: Варианты раскраски соседних клеток в измельчённой сетке Случай 1. C-E. В этом случае E-клетка, покрашена в цвет C-клетки и в цвет соседа C-клетки в исходной сетки. В любом случае, условие выполняется. Случай 2. E-V. В этом случае V-клетка содержит все цвета E-клетки и, возможно, ещё какие-то. Случай 3. C-V. В этом случае V-клетка содержит цвет C-клетки и, возможно, ещё какие-то. Случай 4. E-E. В этом случае либо конфликта нет, либо он есть, но тогда смежная с 𝐸1 и 𝐸2 V-клетка должна быть покрашена во все 3 цвета и мы сразу нашли то, что искали. Если же условия ККМ-раскраски соблюдаются, то в новой сетке найдётся квадратик, покрашенный во все три цвета. Это может быть только V-клетка, а значит мы нашли узел исходной сетки, у которого есть соседи всех трёх цветов, а значит нашли решение для 2D-SPERNER. 25

5.3 DISCRETE-KKM лежит в PPAD 5.3 5 ПОЛНОТА В PPAD DISCRETE-KKM лежит в PPAD Аналогично задаче 2D-KKM можно сформулировать задачу DISCRETEKKM в пространстве любой размерности. Определение 9. Задача DISCRETE-KKM Пусть дана квадратная сетка 𝐾 ˆ . . . ˆ 𝐾 и её раскраска в цвета t0, 1, . . . , 𝑛u задана с помощью схеloooooomoooooon 𝑛 мы полиномиального размера 𝐶. Чтобы интерпретировать выход этой схемы, как раскраску клетки, будем брать это значение по модулю 2𝑛`1 , а получившееся значение будем считать битовой маской, кодирующей раскраску клетки. Задачей DISCRETE-KKM будем называть задачу поиска по 𝐶 либо кубика сетки, покрашенного во все цвета, либо места, где нарушаются правила ККМ-раскраски. Перед доказательством принадлежности этой задачи классу PPAD, докажем, что задача CUBIC-SPERNER (аналог задачи 2D-SPERNER) тоже лежит в PPAD. Теорема 6. CUBIC-SPERNER P PPAD Доказательство. Доказательство этой теоремы можно найти, например, в [5]. Теорема 7. Задача DISCRETE-KKM в пространствах размерности 3 и выше лежит в PPAD. Доказательство. Доказательство этого факта мы проведём, также сводя к CUBIC-SPERNER в пространстве произвольной размерности. Последняя лежит в PPAD в силу Теоремы 7. Сведение будет аналогично двумерному случаю, а именно если кубик из ККМ-раскраски покрашен в цвета 𝑐1 , 𝑐2 , . . . , 𝑐𝑟 , то соответствующий ему кубик в шпернеровской раскраске мы будем красить в min1ď𝑖ď𝑟 𝑐𝑖 . Докажем, что получившаяся по такому правилу раскраска будет шпернеровской: ∙ Нулевой кубик всегда покрашен в цвет 0, а значит и в новой раскраске будет покрашен в цвет 0. 26

5.3 DISCRETE-KKM лежит в PPAD 5 ПОЛНОТА В PPAD ∙ Кубики, у которых одна координата (𝑖-я) равна 𝐾 ´ 1, а все остальные координаты нулевые в исходной раскраске покрашен в цвет 𝑖 и только, а значит в новой раскраске он также раскрашен в цвет 𝑖. ∙ Рассмотрим кубик, у которого какие-то координаты нулевые и не рассмотренный ранее. Пусть его ненулевые координаты имеют номера 𝑖1 , . . . , 𝑖𝑝 . Тогда в новой раскраске этот кубик может быть покрашен в любой из соответствующих цветов, а также в нулевой цвет, но только если среди координат нет ни одной, равной 𝐾 ´ 1. В любом случае, в новой раскраске этот кубик не может иметь цвет, соответствующий ни одной из равных нулю координат. ∙ В новой раскраске кубик, у которого хотя бы одна координата равна 𝐾 ´ 1, не будет покрашен в 0 цвет, поскольку иначе в исходной раскраске он был покрашен в 0 цвет (и, возможно, другие), но такие кубики в ККМ-раскраске не могут иметь координаты, равные 𝐾 ´ 1 по определению дискретной ККМ-раскраски. Поскольку получившаяся раскраска является шпернеровской, то найдётся узел сетки, среди соседей которого встречаются все цвета. Соседи этого узла образуют клику, в которой присутствуют все новые цвета, а мы строили новые цвета так, что кубик покрашенный в цвет 𝑖 в новой раскраске обязательно покрашен в цвет 𝑖 в исходной раскраске. Значит, мы нашли клику, в которой в исходной раскраске присутствуют все цвета, а значит найдётся кубик, который в исходной ККМ-раскраске был покрашен во все цвета, тем самым решив исходную задачу. 27

6 6 ЗАКЛЮЧЕНИЕ Заключение В этой работе мы сформулировали и доказали ККМ-лемму в дискретной постановке в пространстве произвольной размерности. Кроме этого, мы сформулировали вычислительную задачу и показали её полноту в классе PPAD в случае двумерной сетки, а в случае пространств большей размерности доказали принадлежность соответствующей задачи тому же классу PPAD. По итогам работы остаются открытыми следующие вопросы: ∙ Возможно ли ослабить условия в многомерной дискретной ККМлемме (Теорема 4)? ∙ Возможно ли ослабить условия в двумерной дискретной ККМ-лемме, чтобы соответствующая задача всё ещё была полна в PPAD? ∙ Полны ли соответствующие вычислительные задачи в случае пространств размерности 3 и выше? ∙ Существуют ли другие дискретные версии ККМ-леммы, которые полны в классах PPA ил PPADS? 28

СПИСОК ЛИТЕРАТУРЫ Cписок литературы [1] L.E.J Brower. „Über Abbildung von Mannigfaltigkeiten“. Deutsch. In: Mathematische Annalen 71 (1911), S. 97–115. doi: 10.1007/BF01456931. [2] Emanuel Sperner. „Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes“. Deutsch. In: Abh. Math. Sem. Hamburg (1928), S. 265–272. [3] B. Knaster, C. Kuratowski und S. Mazurkiewicz. „Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe“. Deutsch. In: Fundamenta Mathematicae 14.1 (1929), S. 132–137. issn: 0016-2736 1730-6329. doi: 10.4064/fm-14-1-132-137. [4] Kuhn H.W. «Some Combinatorial Lemmas in Topology». англ. в: IBM Journal of Research and Development 4.5 (1960), с. 518—524. issn: 0018-8646. doi: 10.1147/rd.45.0518. [5] Christos H. Papadimitriou. «On the complexity of the parity argument and other inefficient proofs of existence». англ. в: Journal of Computer and System Sciences 48.3 (1994), с. 498—532. doi: 10.1016/S00220000(05)80063-7. [6] P. Jean-Jacques Herings и Adolphus J. J. Talman. «Intersection Theorems with a Continuum of Intersection Points». в: Journal of Optimization Theory and Applications 96 (1998), с. 311—335. [7] Xi Chen и Xiaotie Deng. «3-NASH is PPAD-complete”». в: Electronic Colloquium on Computational Complexity (ECCC) (янв. 2005). [8] Konstantinos Daskalakis и Christos Papadimitriou. «Three-Player Games Are Hard». в: Electronic Colloquium on Computational Complexity (ECCC) (2005). [9] Xi Chen и Xiaotie Deng. «Settling the Complexity of Two-Player Nash Equilibrium». в: окт. 2006, с. 261—272. doi: 10.1109/FOCS.2006.69. [10] Xi Chen и Xiaotie Deng. «On the complexity of 2D discrete fixed point problem». англ. в: Theoretical Computer Science 410.44 (2009), с. 4448—4456. doi: 10.1016/j.tcs.2009.07.052. 29

СПИСОК ЛИТЕРАТУРЫ [11] Dömötör Pálvölgyi. “2D-TUCKER Is PPAD-Complete”. English. In: Internet and Network Economics. Ed. by Stefano Leonardi. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009, pp. 569–574. isbn: 9783-642-10841-9. [12] Paul W. Goldberg. A Survey of PPAD-Completeness for Computing Nash Equilibria. 2011. arXiv: 1103.2709 [cs.GT]. [13] Aviv Adler, Constantinos Daskalakis и Erik D. Demaine. «The Complexity of Hex and the Jordan Curve Theorem». в: ICALP. 2016. [14] Steffen Schuldenzucker, Sven Seuken, and Stefano Battiston. “Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-complete”. English. In: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Ed. by Christos H. Papadimitriou. Vol. 67. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017, 32:1–32:20. isbn: 978-3-95977-029-3. doi: 10 . 4230 / LIPIcs . ITCS.2017.32. url: http://drops.dagstuhl.de/opus/volltexte/ 2017/8155. [15] Paul W. Goldberg and Alexandros Hollender. The Hairy Ball Problem is PPAD-Complete. English. 2019. arXiv: 1902.07657 [cs.CC]. [16] Daniil Musatov. «Discrete analogues of the KKM lemma and their computational complexity». 3rd Hungarian-Russian Combinatorics workshop (22 мая 2019). [17] Доказательство ККМ-леммы // URL: https://planetmath.org/kkmlemma. [18] Даниил Мусатов. Сложность вычислений. Классика и современность. 30