La complexité de trouver un point Borsuk-Ulam

10

Le théorème de Borsuk-Ulam dit que pour chaque fonction impaire continue g d'une sphère n dans un espace n euclidien, il y a un point x0 tel que g(X0)=0 .

Simmons et Su (2002) décrivent une méthode pour approximer le point X0 utilisant le lemme de Tucker . Cependant, la complexité d'exécution de leur méthode n'est pas claire.

Supposons que l'on nous donne un oracle pour la fonction g et un facteur d'approximation ϵ>0 . Quelle est la complexité d'exécution (en fonction de n ) de:

  1. Trouver un point X tel |g(X)|<ϵ ?
  2. Trouver un point X tel que |X-X0|<ϵ , lorsque X0 est un point satisfaisant g(X0)=0 ?
Erel Segal-Halevi
la source
1
Est-ce sur une vraie machine RAM ?

Réponses:

5

Papadimitriou a montré qu'une version de ce problème est PPAD-complete dans l'article présentant cette classe, "Sur la complexité de l'argument de la parité et d'autres preuves d'existence inefficaces" .

Sa formulation du problème est la suivante:

Borsuk-Ulam. Soit un entier n et une machine de Turing calculant pour chaque point avec - n x in et max | x i | = n (la surface de la sphère ), une fonction avec . Trouver un avec .P=(X1,,X)-nXjenmax|Xje|=nL1F(p)F(p)1KnX|F(X)-F(-X)|1n2

(Sidenote - plusieurs fois lorsque vous voyez un type de théorème à virgule fixe, PPAD est une bonne estimation de la complexité de le trouver ...)

usul
la source
4

Comment l'oracle est-il donné et que savons-nous de ? Si l'oracle est à boîte noire et que nous savons seulement que g est impair continu, alors déjà pour n = 1, nous pourrions exiger une infinité de questions ...ggn=1

Si l'oracle est donné par une machine Turing, alors vous obtenez que votre problème est

  1. FIXP-complete,

  2. PPAD-complet,

ϵ

domotorp
la source