Go backward to 23 Isomorphism of Vertex-Facet Incidences
Go up to 4 Isomorphism
|
Go backward to 23 Isomorphism of Vertex-Facet Incidences Go up to 4 Isomorphism |
XHTML 1.0 |
| Input: | Face Lattice of a polytope P |
|---|---|
| Output: | "Yes" if P is isomorphic to its dual, "No" otherwise |
| Status (general): | Open |
|---|---|
| Status (fixed dim.): | Polynomial time |
|
This is a special case of problem 22. In
particular, it is solvable in polynomial time in bounded
dimensions.
It is easy to see that deciding whether a general 0/1-matrix A (not necessarily a vertex-facet incidence matrix of a polytope) can be transformed into AT by permuting its rows and columns is graph isomorphism complete. |
| Related problems: | 22 |
|---|
|
|
Why are some symbols not displayed correctly? |