On the computational complexity of Betti numbers: reductions from matrix rank
Herbert Edelsbrunner, Salman Parsa · 2014
We give evidence for the difficulty of computing Betti numbers of simplicial complexes over a finite field. We do this by reducing the rank computation for sparse matrices with m non-zero entries to computing Betti numbers of simplicial complexes consisting of at most a constant times m simplices. Together with the known reduction in the other direction, this implies that the two problems have the same computational complexity.