Two polytopes *P _{1} Ì R^{d1}* and

As soon as one starts to investigate structural properties of polytopes by means of computer programs, algorithms for deciding whether two polytopes are isomorphic become relevant.

Some problems in this section are known to be hard in the sense that
the *graph isomorphism problem* can polynomially be reduced to
them. Although this problem is not known (and even not expected) to be
*NP*-complete, all attempts to find a polynomial time algorithm for
it have failed so far. Actually, the same holds for a lot of problems
that can be polynomially reduced to the graph isomorphism problem
(see, e.g., Babai [3]).