Abstract:

We prove that Euler characteristic is #P-complete and present a new algorithm for computing Euler characteristic. The talk does not assume any background beyond an understanding of the complexity class NP. The complexity of Euler characteristic has previously been studied in a geometric setting where the complexes are described in terms of compact representations of polytopes. We consider the general case where the input is an abstract simplicial complex represented by a list of all vertices and facets. With this input representation the Euler characteristic problem becomes purely combinatorial and we show that the problem remains #P-complete even though the representation is more verbose. For example a hypercube has 2^n vertices and only 2n facets, so describing just the facets makes for much smaller input.

This is joint work with Eduardo Saenz De Cabezon.