¿Puede calcularse el rango del grupo homológico de un complejo simplicial abstracto en tiempo polinómico?

Question

Quiero escribir una función que haga lo siguiente:

Entrada:

1. Un número entero $n$
2. Una función $f$ que asigna subconjuntos no vacíos de $\{1, \dots, n\}$ a "sí" o "no", de manera que (a) todo conjunto único obtiene "sí", y (b) si algún conjunto obtiene "sí", entonces todos sus subconjuntos también obtienen "sí".
3. Un número entero $k \le n$

Juntas, estas dos entradas definen un complejo simplicial abstracto.

La salida:

1. El rango del grupo de homología $H_k$ del complejo simplicial.

Quiero una función que sea polinómica en el valor de $n$ (no el tamaño de la representación en bits de $n$ ) que resuelve este problema. ¿Se puede hacer esto?

Answer 1

Un argumento de conteo sugiere que esto no es cierto, ya que hay $2^{2^n}$ complejos, y con el tiempo $P(n)$ no se puede, en cierto modo, utilizar toda la entrada.

Por ejemplo, para conocer el número de generadores de la homología de dimensión superior, en el caso de que todos los símbolos máximos sean de cardinalidad $[n/2]$ se necesita saber cuántos símiles máximos hay, y podría ser la cardinalidad de un subconjunto arbitrario de un conjunto de tamaño ${n \choose {[n/2]}} \hskip3pt$ . No veo cómo hacerlo sin comprobar por fuerza bruta todas las posibilidades, cuyo número es exponencial en $n$ .

Answer 2

La homología puede ser calculada en tiempo polinómico en el número de símiles - esto es sólo un cálculo de la forma normal de Smith - pero eso no es lo mismo que polinómico en $n.$