5 added 10 characters in body

Given a set $A$ of subsets of ${1, \ldots n}$ which is closed under taking subsets, let $X(A)$ be the corresponding simplicial complex, i.e. simplices of $X(A)$ are elements of the set $\bar A$, and gluing is induced by containment of subsets)

Consider the following computational problem

Input: a natural number $n$ and two sets $A$ and $B$ of subsets of ${1,\ldots, n}$, closed under taking subsets.

Problem: Are $X(A)$ and $X(B)$ isomorphic as simplicial complexes? (i.e. is there a bijection of ${1,\ldots ,n}$ which bijectively sends faces of $X(A)$ to faces of $X(B)$?)

Question: I'm interested to know what algorithms are known for this problem. I'm specifically interested in worst running times in terms of $n$ alone. Please note that the size of the input can be exponential in $n$.

In principle the input $A$ and $B$ might consist of $2^n$, 2^n$subsets, so this is a lower bound for the problem, because the algorithm needs to read the input. On the other hand the trivial algorithm of checking each permutation takes at most$\mathcal O(2^n\cdot n!)$steps. 4 deleted 861 characters in body One can obviously express instances of In principle the graph isomorphism problem as instances input might consist of the problem above, by considering 1-dimensional simplicial complex. So one shouldn'h hope for an algorithm which takes less than$2^{\mathcal O(\sqrt{n\cdot log(n)}})$steps in the worst case (2^n$, so this is a lower bound taken from wikipedia).

Conversely, one can also express instances of for the problem above as graph isomorphism problem, by adding additional vertex for each face, and joining the vertices of the given face with because the additional vertex (and perhaps doing something funny with this vertex as to assure that graph isomorphism must map additional vertices corresponding to k-dimensional faces in one graph to additional vertices corresponding algorithm needs to k-dimensional faces in read the other graph)input.This produces a graph which can have as many as $2^n+n$ vertices, so this leads to an

On the other hand the trivial algorithm with running time bounded by of checking each permutation takes at most $2^{\mathcal O(\sqrt{2^n\cdot n\cdot log(2)}})$. Of course it's not clear if this algorithm really is so bad, as the resulting graphs are very special\mathcal O(2^n\cdot n!)$steps. 3 clarification Given a set$A$of subsets of${1, \ldots n}$which is closed under taking subsets, let$X(A)$be the corresponding simplicial complex, i.e. simplices of$X(A)$are elements of the set$\bar A$, and gluing is induced by containment of subsets) Consider the following computational problem Input: a natural number$n$and two sets$A$and$B$of subsets of${1,\ldots, n}$, closed under taking subsets. Problem: Are$X(A)$and$X(B)$isomorphic as simplicial complexes? (i.e. is there a bijection of${1,\ldots ,n}$which bijectively sends faces of$X(A)$to faces of$X(B)$?) Question: I'm interested to know what algorithms are known for this problem. I'm specifically interested in worst running times in terms of$n$alone. Please note that the size of the input can be exponential in$n$. One can obviously express instances of the graph isomorphism problem as instances of the problem above, by considering 1-dimensional simplicial complex. So one shouldn'h hope for an algorithm which takes less than$2^{\mathcal O(\sqrt{n\cdot log(n)}})$steps in the worst case (bound taken from wikipedia). Conversely, one can also express instances of the problem above as graph isomorphism problem, by adding additional vertex for each face, and joining the vertices of the given face with the additional vertex (and perhaps doing something funny with this vertex as to assure that graph isomorphism must map additional vertices corresponding to k-dimensional faces in one graph to additional vertices corresponding to k-dimensional faces in the other graph). This produces a graph which can have as many as$2^n+n$vertices, so this leads to an algorithm with running time bounded by$2^{\mathcal O(\sqrt{2^n\cdot n\cdot log(2)}})\$. Of course it's not clear if this algorithm really is so bad, as the resulting graphs are very special.

2 deleted 48 characters in body
1