Problema de reconocimiento complejo simplicial

El problema del reconocimiento de complejos simpliciales es un problema computacional en topología algebraica . Dado un complejo simplicial , el problema consiste en decidir si es homeomorfo a otro complejo simplicial fijo. El problema es indecidible para complejos de dimensión 5 o superior. ^{[ 1 ] [ 2 ] : 9–11}

Un complejo simplicial abstracto (CSA) es una familia de conjuntos cerrada bajo la operación de subconjuntos (un subconjunto de un conjunto de la familia también pertenece a la misma familia). Todo complejo simplicial abstracto tiene una única realización geométrica en un espacio euclidiano como complejo simplicial geométrico (CSG), donde cada conjunto con k elementos en el CSA se mapea a un simplex de dimensión ( k − 1) en el CSG. Por lo tanto, un CSA proporciona una representación finita de un objeto geométrico. Dado un CSA, se pueden plantear varias preguntas sobre la topología del CSG que representa.

El problema del homeomorfismo es: dados dos complejos simpliciales finitos que representan variedades diferenciables , decidir si son homeomorfos .

• Si los complejos tienen una dimensión como máximo 3, entonces el problema es decidible. Esto se deduce de la demostración de la conjetura de geometrización .
• Para todo d ≥ 4, el problema del homeomorfismo para complejos simpliciales d -dimensionales es indecidible. ^{[ 3 ]}

Lo mismo ocurre si se reemplaza "homeomorfo" por " homeomorfo lineal por partes ".

El problema del reconocimiento es un subproblema del problema de homeomorfismo, en el que se da un complejo simplicial como parámetro fijo. Dado otro complejo simplicial como entrada, el problema consiste en decidir si es homeomorfo al complejo fijo dado.

• El problema de reconocimiento es decidible para la esfera tridimensional.${\displaystyle S^{3}}$. ^{[ 4 ]} Es decir, existe un algoritmo que puede decidir si un complejo simplicial dado es homeomorfo al límite de una bola de 4 dimensiones.
• El problema del reconocimiento es indecidible para la esfera d-dimensional.${\displaystyle S^{d}}$para cualquier d ≥ 5. La demostración se realiza por reducción a partir del problema de palabras para grupos . A partir de esto, se puede demostrar que el problema de reconocimiento es indecidible para cualquier variedad compacta d -dimensional fija con d ≥ 5.
• A partir de 2014, sigue abierto el debate sobre si el problema del reconocimiento es decidible para la esfera de 4 dimensiones.${\displaystyle S^{4}}$. ^{[ 2 ] : 11}

El problema de la variedad es: dado un complejo simplicial finito, ¿es homeomorfo a una variedad ? El problema es indecidible; la demostración se realiza por reducción a partir del problema de la palabra para grupos . ^{[ 2 ] : 11}