La complejidad de encontrar un punto Borsuk-Ulam

10

El teorema de Borsuk-Ulam dice que por cada función impar continua sol desde una esfera n al espacio n euclidiano, hay un punto X0 0 tal que sol(X0 0)=0 0 .

Simmons y Su (2002) describen un método para aproximar el punto X0 0 usando el lema de Tucker . Sin embargo, no está claro cuál es la complejidad en tiempo de ejecución de su método.

Supongamos que se nos da un oráculo para la función sol un factor de aproximación ϵ>0 0 . ¿Cuál es la complejidad del tiempo de ejecución (en función de norte ) de:

  1. Encontrar un punto X tal El |sol(X)El |<ϵ ?
  2. Encontrar un punto X tal que el El |X-X0 0El |<ϵ , cuando es un punto que satisface g ( x 0 ) = 0 ?X0 0sol(X0 0)=0 0
Erel Segal-Halevi
fuente
1
¿Está esto en una máquina de RAM real ?

Respuestas:

5

Papadimitriou demostró que una versión de este problema está completa en PPAD en el documento que presenta esa clase, "Sobre la complejidad del argumento de paridad y otras pruebas ineficaces de existencia" .

Su formulación del problema es:

Borsuk-Ulam. Dado un entero n y una máquina de Turing que computa para cada punto con - n f ( p ) 1P=(x1,,xd) y max | x i | = n (la superficie de laesfera), una funcióncon. Encuentre unacon.nxinmax|xi|=nL1f(p) x| f(x)-f(-x)| 1f(p)1Knx|f(x)f(x)|1n2

(Nota al margen: muchas veces cuando ves un tipo de teorema de punto fijo, PPAD es una buena suposición por la complejidad de encontrarlo ...)

usul
fuente
4

¿Cómo se da el oráculo y qué sabemos sobre ? Si el oráculo es de caja negra y solo sabemos que g es impar continuo, entonces ya para n = 1 podríamos requerir infinitas preguntas ...solsolnorte=1

Si el oráculo es dado por alguna máquina de Turing, entonces usted entiende que su problema

  1. FIXP-complete,

  2. PPAD completo,

ϵ

domotorp
fuente