Теорема Борсука-Улама говорит, что для любой непрерывной нечетной функции из n-сферы в евклидово n-пространство существует точка такая, что .х 0 г ( х 0 ) = 0
Simmons и Su (2002) описывают метод аппроксимации точки с использованием леммы Такера . Однако не ясно, какова сложность их метода во время выполнения.
Предположим, нам дан оракул для функции и коэффициент приближения . Что такое сложность во время выполнения (как функция от ):ε > 0 п
- Нахождение точки такой ?| г ( х ) | < ϵ
- Находим точку такую, что , когда - точка, удовлетворяющая ?| х - х 0 | < ϵ x 0 г ( x 0 ) = 0
approximation-algorithms
time-complexity
topology
algebraic-topology
Эрель Сегал-Халеви
источник
источник
Ответы:
Пападимитриу показал, что версия этой проблемы является PPAD-полной в статье, посвященной этому классу: «О сложности аргумента четности и других неэффективных доказательствах существования» .
Его формулировка проблемы такова:
(Замечание - во многих случаях, когда вы видите теорему с фиксированной точкой, PPAD является хорошим предположением для сложности ее нахождения ...)
источник
Как дается оракул и что мы знаем о ? Если оракул является черным ящиком, и мы знаем только, что непрерывно нечетно, то уже при нам может потребоваться бесконечно много вопросов ...г н = 1g g n=1
Если оракул дается какой-то машиной Тьюринга, то вы понимаете, что ваша проблема
FIXP-полной,
PPAD-полной,
где размер ввода - длина . Для ознакомления с ними см. Http://homepages.inf.ed.ac.uk/kousha/dagstuhl14-etessami-tutorial-equilibrium.pdf .ϵ
источник