Exercise 1 pag. 90 of "Computational Topology" by H. Edelsbrunner:
What is the computational complexity of recognizing isomorphic abstract simplicial complexes?
The question isn't completely formalized, so I just ask for an idea.
My intuition is that for a simplicial complex that is generated by $n$ maximal simplices the complexity is $2^n$. With maximal I mean that nobody of them is a proper face of any other. The reason is the that i need to consider all their possible intersections $\sum_{k=0}^n \binom{n}{k}=2^n$.
For example given two isomorphic simplicial complexes, we define an arbitraty bijection between the vertex that are in the intersection of every $n$ simplices. Then taken a set that is the intersection of $n-1$ simplices, there will be $k$ unassigned vertex, we look for a set in the same state an make an arbitraty assignment and so on...
Can you confirm my ideas?