backup

Go backward to 23 Isomorphism of Vertex-Facet Incidences
Go up to 4 Isomorphism
XHTML 1.0

24 Selfduality of Polytopes

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.


backup Why are some symbols not displayed correctly?