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