| Input: | Finite abstract simplicial complex D given by a list of facets |
|---|---|
| Output: | Euler characteristic c(D) Î Z |
| Status (general): | Open |
|---|---|
| Status (fixed dim.): | Polynomial time |
|
It is unknown whether the decision version "c(D) = 0?"
of this problem is in NP. The problem is easy if D is
given by a list of all of its simplices. For fixed dimension, one
can enumerate all simplices of D and compute the Euler
characteristic in polynomial time.
Currently the fastest way to compute the Euler characteristic is to first generate (the Hasse diagram of) V = {S : S is an intersection of facets of D} in time O(min{n,m} · a· | V |), see [33], where a is the number of incidences between vertices and facets of D. In the next step one can compute c(D) in the same time by computing the Möbius function of V, see Rota [56] and [53]. Usually V is much smaller than the whole face lattice of D. Furthermore, if computing c(D) is NP-hard, then it is NP-hard for pure complexes, see [53]. |
| Related problems: | 33 |
|---|