Can the rank of the homology group of an abstract simplicial complex be computed in polynomial time?

Question

I want to write a function that does the following:

Input:

1. An integer $n$
2. A function $f$ that maps nonempty subsets of $\{1, \dots, n\}$ to "yes" or "no" such that (a) every singleton set gets "yes," and (b) if any set gets "yes" then all its subsets get "yes" too.
3. An integer $k \le n$

Jointly, these two inputs define an abstract simplicial complex.

Output:

1. The rank of the homology group $H_k$ of the simplicial complex.

I want a function that is polynomial in the value of $n$ (not the size of the bit representation of $n$) that solves this problem. Can this be done?

Answer 1

A counting argument suggests this is not true, as there are $2^{2^n}$ complexes , and in time $P(n)$ you cannot, in some sense, use all of the input.

For instance, to know the number of generators of the top dimensional homology, in the case where all maximal simplices are of cardinality $[n/2]$, you need to know how many maximal simplices there are, and it could be the cardinality of an arbitrary subset of a set of size ${n \choose {[n/2]}} \hskip3pt$. I don't see how to do that without brute force checking of all possibilities, whose number is exponential in $n$.

Answer 2

Homology can be computed in polynomial time in the number of simplices -- this is just a Smith normal form computation -- but that is not the same thing as polynomial in $n.$