Die Komplexität, einen Borsuk-Ulam-Punkt zu finden

10

Das Borsuk-Ulam-Theorem besagt, dass es für jede stetige ungerade Funktion g von einer n-Kugel in den euklidischen n-Raum einen Punkt x0 so dass g(x0)=0 .

Simmons und Su (2002) beschreiben eine Methode zur Approximation des Punktes x0 Verwendung von Tuckers Lemma . Es ist jedoch nicht klar, wie komplex ihre Methode zur Laufzeit ist.

Angenommen, wir erhalten ein Orakel für die Funktion g und einen Approximationsfaktor ϵ>0 . Was ist die Laufzeitkomplexität (als Funktion von n ) von:

  1. Finden eines Punktes x wie |g(x)|<ϵ ?
  2. Finden eines Punktes x so dass die |xx0|<ϵ , wenn x0 ein Punkt ist, der erfüllt g(x0)=0?
Erel Segal-Halevi
quelle
1
Ist das auf einem Real RAM Computer?

Antworten:

5

Papadimitriou hat gezeigt, dass eine Version dieses Problems PPAD-vollständig ist, in dem Artikel, in dem diese Klasse vorgestellt wird: "Über die Komplexität des Paritätsarguments und andere ineffiziente Existenznachweise" .

Seine Formulierung des Problems lautet:

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

(Nebenbemerkung - oft, wenn Sie einen Satz mit festem Punkt sehen, ist PPAD eine gute Vermutung für die Komplexität des Findens ...)

usul
quelle
4

Wie wird das Orakel gegeben und was wissen wir über ? Wenn das Orakel eine Blackbox ist und wir nur wissen, dass stetig ungerade ist, dann benötigen wir bereits für unendlich viele Fragen ...g n = 1ggn=1

Wenn das Orakel von einer Turing-Maschine gegeben wird, dann bekommen Sie, dass Ihr Problem ist

  1. FIXP-vollständig,

  2. PPAD-vollständig,

Dabei ist die Größe der Eingabe die Länge von . Eine Einführung in diese finden Sie unter http://homepages.inf.ed.ac.uk/kousha/dagstuhl14-etessami-tutorial-equilibrium.pdf .ϵ

domotorp
quelle