El teorema de Borsuk-Ulam dice que por cada función impar continua desde una esfera n al espacio n euclidiano, hay un punto tal que .
Simmons y Su (2002) describen un método para aproximar el punto 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 un factor de aproximación . ¿Cuál es la complejidad del tiempo de ejecución (en función de ) de:
- Encontrar un punto tal ?
- Encontrar un punto tal que el , cuando es un punto que satisface g ( x 0 ) = 0 ?
approximation-algorithms
time-complexity
topology
algebraic-topology
Erel Segal-Halevi
fuente
fuente
Respuestas:
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:
(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 ...)
fuente
¿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 ...sol sol n = 1
Si el oráculo es dado por alguna máquina de Turing, entonces usted entiende que su problema
FIXP-complete,
PPAD completo,
fuente