Problemas topológicos sin solución algorítmica

Question

Esta pregunta se inspira en un artículo de B. Poonen que apareció en el arxiv hace algún tiempo: http://arxiv.org/abs/1204.0299 . El documento ofrece una muestra de problemas algorítmicamente irresolubles de diversas áreas de las matemáticas.

La parte de topología, sin embargo, sólo contiene dos problemas de este tipo: el problema del homeomorfismo para los 4-manifolds, que Markov demostró que era indecidalbe en 1958, y el problema de reconocer $S^n,n\geq 5$ hasta homeomorfismo. La indecidibilidad en ambos casos se reduce básicamente a la indecidibilidad del problema del isomorfismo de grupo.

Obsérvese que los dos problemas anteriores son decidibles si se limita la atención a los manifolds PL simplemente conectados. Esto se deduce, en el primer caso, del hecho de que los 4-manifolds PL simplemente conectados están determinados hasta el homeomorfismo por la cohomología integral y, en el segundo caso, de la conjetura generalizada de Poincare.

Esto hace que uno se pregunte qué ocurre si se imponen algunas restricciones topológicas naturales como la simple conectividad. Así que me gustaría preguntar si los siguientes problemas son decidibles para los complejos simpliciales finitos simplemente conectados, tal vez bajo algunas restricciones adicionales (por ejemplo, para aquellos complejos simpliciales que son homeomorfos a suaves o PL-manifolds):

• el problema del homeomorfismo

• el problema de la equivalencia homotópica

• el racional (o mod a prime $p$ ) problema de equivalencia homotópica

Personalmente, no tengo muchas esperanzas de que ninguna de ellas resulte decidible algorítmicamente. Por ejemplo, el tipo de homotopía racional de un espacio $X$ puede verse como una colección infinita de mapas $H^{\otimes n}\to H$ de grados $2-n$ (donde $H=H^*(X,\mathbb{Q})$ ) sujeta a alguna condición, hasta una relación de equivalencia, y parece plausible que todos los componentes de esta colección importen. Sin embargo, no tengo muy claro cómo demostrarlo.

Answer 1

Ayer presentamos en http://arxiv.org/abs/1302.2370 un artículo titulado "Extendability of continuous maps is undecidable" en el que se afirma que el siguiente problema es indecidible: Dados complejos simpliciales $X$ y $Y$ y un mapa simplicial $f:A\to Y$ de un subcomplejo $A$ de $X$ decidir si existe una extensión continua $|X|\to |Y|$ de $|f|$ . Características sustanciales:

• la indecibilidad se demuestra mediante una reducción a partir del décimo problema de Hilbert, es decir, la resolubilidad de la ecuación polinómica diofantina

• la indecidibilidad se mantiene incluso si exigimos que los espacios considerados sean $k$ -conectado para arbitrario $k\ge 1$

En particular, una vez que la dimensión de $X$ es inferior a $2k$ donde $k$ es la conectividad de $Y$ (rango estable), el problema se resuelve (en tiempo polinómico cuando $k$ es fijo), véase http://arxiv.org/abs/1211.3093 .

Answer 2

Me parece bastante claro que si arreglas $n$ y nos fijamos en complejos simpliciales n-dimensionales finitos simplemente conectados, entonces el problema de equivalencia homotópica (racional) es decidible. Está bastante claro que la construcción de torres (racionales) de Postnikov es algorítmica. Comparar dos torres de Postnikov es una secuencia de problemas de obstrucción, cada uno decidible. Y no es necesario comparar torres de Postnikov completas, basta con comparar hasta la altura $n$ (el resto se determina automáticamente).

Answer 3

De "Hardness of embedding simplicial complexes in $\mathbb{R}^d$ ," por Matoušek, Tancer, Wagner, 2009 ( Enlace de descarga del PDF ):

Según un célebre resultado de Novikov ([VKF74]; véase también, por ejemplo, [Nab95] para una exposición), el siguiente problema es algorítmicamente irresoluble: Dado un $d$ -dimensional complejo simplicial, $d \ge 5$ decidir si es homeomorfo a $\mathbb{S}^d$ , el $d$ -esfera dimensional.

• [VKF74] I.A. Volodin, V.E. Kuznetsov y A.T. Fomenko. El problema de discriminar algorítmicamente la esfera tridimensional estándar. Usp. Mat. Nauk , 29(5):71-168, 1974. En ruso. Traducción al inglés: Russ. Math. Surv. 29,5:71-172 (1974).
• [Nab95] A. Nabutovsky. Estructuras de Einstein: Existencia versus unicidad. Geom. Funct. Anal. , 5(1):76-91, 1995.

En su artículo, demuestran que decidir si un complejo simplicial finito $K$ de dimensión como máximo $k$ se puede incrustar (linealmente a trozos) en $\mathbb{R}^d$ es NP-difícil, para todo $k, d$ con $d \ge 4$ y $d \ge k \ge (2d− 2)/3$ .