
Тип работы:	Предмет:	Язык работы:

Теория неподвижных точек

Работа №	74774
Тип работы	Дипломные работы, ВКР
Предмет	математика
Объем работы	30
Год сдачи	2020
Стоимость	4750 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	45

Не подходит работа?

Узнай цену на написание

Содержание

1 Введение 3
1.1 Используемые определения 3
1.2 Известные результаты 4
1.3 ККМ-лемма 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
Описок литературы

Введение

В этой работе мы сформулируем и решим задачу, находящуюся на пересечение двух больших областей науки — теории неподвижных точек и теории сложности вычислений. Теория неподвижных точек изучает теоремы, которые гарантируют наличие неподвижных точек (это понятие определяется по-разному в зависимости от теоремы). Классическим результатом в этой области является теорема Брауэра о неподвижной точке [1], которая гласит, что у любого непрерывного отображения шара самого в себя найдётся неподвижная точка. Многие задачи этой теории имеют соответствующие вычислительные задачи, которые лежат и полны в сложностном классе PPAD, введённом Пападимитриу в [5].

Возникли сложности?

Нужна помощь преподавателя?

Помощь студентам в написании работ!

ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ

Курсовые Статьи Диплом Рязань

Заключение

В этой работе мы сформулировали и доказали ККМ-лемму в дискретной постановке в пространстве произвольной размерности. Кроме этого, мы сформулировали вычислительную задачу и показали её полноту в классе PPAD в случае двумерной сетки, а в случае пространств большей раз¬мерности доказали принадлежность соответствующей задачи тому же классу PPAD.
По итогам работы остаются открытыми следующие вопросы:
• Возможно ли ослабить условия в многомерной дискретной ККМ- лемме (Теорема 4)?
• Возможно ли ослабить условия в двумерной дискретной ККМ-лемме, чтобы соответствующая задача всё ещё была полна в PPAD?
• Полны ли соответствующие вычислительные задачи в случае пространств размерности 3 и выше?
• Существуют ли другие дискретные версии ККМ-леммы, которые полны в классах PPA ил PPADS?

Литература

[1] L.E.J Brower. „Uber Abbildung von Mannigfaltigkeiten“. Deutsch. In: Mathematische Annalen 71 (1911), S. 97-115. doi: 10.1007/BF01456931.
[2] Emanuel Sperner. „Neuer Beweis fur 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 Fix- punktsatzes fur 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/S0022- 0000(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.
[11] Domotor Palvolgyi. “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: 978¬3-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 Com¬puter Science Conference (ITCS 2017). Ed. by Christos H. Papadim- itriou. 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] Даниил Мусатов. Сложность вычислений. Классика и современ¬ность.