Kompleksitas menemukan titik Borsuk-Ulam

The Borsuk-Ulam Teorema mengatakan bahwa untuk setiap terus menerus aneh fungsi dari n-bola ke dalam Euclidean n-space, ada titik sehingga .x 0 g ( x 0 ) = $g$$x_0$$g(x_0)=0$

Simmons dan Su (2002) menjelaskan metode untuk memperkirakan titik menggunakan lemma Tucker . Namun, tidak jelas apa kompleksitas run-time dari metode mereka.$x_0$

Misalkan kita diberi oracle untuk fungsi dan faktor aproksimasi . Apa kompleksitas run-time (sebagai fungsi dari ) dari:ϵ > 0 $g$$\epsilon>0$$n$

1. Menemukan titik seperti ?| g ( x ) | < $x$$|g(x)|<\epsilon$
2. Menemukan titik sedemikian rupa sehingga , ketika adalah titik yang memuaskan ?| x - x 0 | < ϵ x 0 g ( x 0 ) = $x$$|x-x_0|<\epsilon$$x_0$$g(x_0)=0$

Papadimitriou menunjukkan bahwa versi dari masalah ini adalah PPAD-lengkap dalam makalah yang memperkenalkan kelas itu, "Tentang kompleksitas argumen paritas dan bukti keberadaan yang tidak efisien lainnya" .

Rumusan masalahnya adalah:

Borsuk-Ulam. Diberikan bilangan bulat n dan mesin Turing yang menghitung untuk setiap titik dengan dan (permukaan bola ), sebuah fungsi dengan . Cari dengan .- n ≤ x i ≤ n max | x i | = n L 1 f ( p ) f ( p ) ≤ $P=(x_1,\dots,x_d)$$-n\leq x_i\leq n$$\max_{|x_i|}=n$$L_1$$f(p)$ x| f(x)-f(-x)| ≤$f(p) \leq \frac{1}{Kn}$$x$$|f(x) - f( - x)| \leq \frac{1}{n^2}$

(Sidenote - berkali-kali ketika Anda melihat tipe teorema titik-tetap, PPAD adalah tebakan yang baik untuk kompleksitas menemukannya ...)

Bagaimana oracle itu diberikan dan apa yang kita ketahui tentang ? Jika oracle adalah kotak hitam dan kita hanya tahu bahwa adalah aneh terus menerus, maka sudah untuk kita mungkin memerlukan banyak pertanyaan ...g n = $g$$g$$n=1$

Jika oracle diberikan oleh beberapa mesin Turing, maka Anda mengerti bahwa masalahnya adalah Anda

1. Selesaikan FIXP,

2. PPAD-lengkap,

di mana ukuran input adalah panjang . Untuk pengantar tentang hal ini, lihat http://homepages.inf.ed.ac.uk/kousha/dagstuhl14-etessami-tutorial-equilibrium.pdf .$\epsilon$