Сложность поиска точки Борсук-Улам

10

Теорема Борсука-Улама говорит, что для любой непрерывной нечетной функции из n-сферы в евклидово n-пространство существует точка такая, что .х 0 г ( х 0 ) = 0gx0g(x0)=0

Simmons и Su (2002) описывают метод аппроксимации точки с использованием леммы Такера . Однако не ясно, какова сложность их метода во время выполнения.x0

Предположим, нам дан оракул для функции и коэффициент приближения . Что такое сложность во время выполнения (как функция от ):ε > 0 пgϵ>0n

  1. Нахождение точки такой ?| г ( х ) | < ϵx|g(x)|<ϵ
  2. Находим точку такую, что , когда - точка, удовлетворяющая ?| х - х 0 | < ϵ x 0 г ( x 0 ) = 0x|xx0|<ϵx0g(x0)=0
Эрель Сегал-Халеви
источник
1
Это на реальной машине RAM ?

Ответы:

5

Пападимитриу показал, что версия этой проблемы является PPAD-полной в статье, посвященной этому классу: «О сложности аргумента четности и других неэффективных доказательствах существования» .

Его формулировка проблемы такова:

P=(x1,,xd)nxinL 1 f ( p ) f ( p ) 1max|xi|=nL1f(p) х| f(x)-f(-x)| 1f(p)1Knx|f(x)f(x)|1n2

(Замечание - во многих случаях, когда вы видите теорему с фиксированной точкой, PPAD является хорошим предположением для сложности ее нахождения ...)

усул
источник
4

Как дается оракул и что мы знаем о ? Если оракул является черным ящиком, и мы знаем только, что непрерывно нечетно, то уже при нам может потребоваться бесконечно много вопросов ...г н = 1ggn=1

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

  1. FIXP-полной,

  2. PPAD-полной,

где размер ввода - длина . Для ознакомления с ними см. Http://homepages.inf.ed.ac.uk/kousha/dagstuhl14-etessami-tutorial-equilibrium.pdf .ϵ

domotorp
источник