Złożoność znalezienia punktu Borsuk-Ulam

Twierdzenie Borsuka-Ulama mówi, że dla każdej ciągłej funkcji nieparzystej sfery n do e-przestrzeni istnieje punkt taki, że .x 0 g ( x 0 ) = $g$$x_0$$g(x_0)=0$

Simmons i Su (2002) opisują metodę aproksymacji punktu za pomocą lematu Tuckera . Jednak nie jest jasne, jaka jest złożoność ich metody w czasie wykonywania.$x_0$

Załóżmy, że podano nam wyrocznię dla funkcji współczynnik przybliżenia . Jaka jest złożoność w czasie wykonywania (jako funkcja ):ϵ > 0 $g$$\epsilon>0$$n$

1. Znalezienie punktu taki ?| g ( x ) | < $x$$|g(x)|<\epsilon$
2. Znalezienie punktu takiego, że , gdy jest punktem spełniającym ?| x - x 0 | < ϵ x 0 g ( x 0 ) = $x$$|x-x_0|<\epsilon$$x_0$$g(x_0)=0$

Papadimitriou wykazał, że wersja tego problemu jest kompletna z PPAD w artykule wprowadzającym tę klasę: „O złożoności argumentu parzystości i innych nieefektywnych dowodach istnienia” .

Jego sformułowanie problemu brzmi:

Borsuk-Ulam. Biorąc pod uwagę liczbę całkowitą n i maszynę Turinga obliczającą dla każdego punktu z i (powierzchnia kuli ), funkcja z . Znajdź pomocą .$P=(x_1,\dots,x_d)$$-n\leq x_i\leq n$$\max_{|x_i|}=n$$L_1$$f(p)$$f(p) \leq \frac{1}{Kn}$$x$$|f(x) - f( - x)| \leq \frac{1}{n^2}$

(Sidenote - wiele razy, gdy widzisz twierdzenie o stałym punkcie, PPAD dobrze zgaduje złożoność jego znalezienia ...)

Jak podaje się wyrocznię i co wiemy o ? Jeśli wyrocznia jest czarną skrzynką i wiemy tylko, że jest ciągłym nieparzystym, to już dla możemy wymagać nieskończenie wielu pytań ...$g$$g$$n=1$

Jeśli wyrocznia jest dana przez jakąś maszynę Turinga, wtedy masz problem

1. FIXP-complete,

2. PPAD-complete,

gdzie rozmiar danych wejściowych to długość . Wprowadzenie do nich można znaleźć na stronie http://homepages.inf.ed.ac.uk/kousha/dagstuhl14-etessami-tutorial-equilibrium.pdf .$\epsilon$